Mate

Mate got a string of lowercase English letters from his parents. To get at least some use out of the present, he decided to find rhymes in it for the song he is writing next.

A rhyme is a word of length $D$ whose next to last letter is $X$ and whose last letter is $Y$. Mate builds a word by crossing out some letters of the given string and joining the letters he did not cross out in their original order. For each rhyme, count how many ways there are to cross out letters so that the remaining word meets the condition.

Two ways count as different when the sets of crossed-out positions differ.

The first line contains a string $S$ of lowercase English letters. ($2 \le |S| \le 2000$)

The second line contains the integer $Q$, the number of rhymes Mate needs. ($1 \le Q \le 500\,000$)

Each of the next $Q$ lines contains an integer $D$ and a string $XY$ of two lowercase English letters, separated by a space. ($2 \le D \le |S|$)

Print $Q$ lines. The $i$th line contains the number of ways for the $i$th rhyme. The number can get very large, so print it modulo $1\,000\,000\,007$.

Take $S$ = banana with $D = 2$ and $XY$ = na. Number the letters from 1. Exactly three sets of kept positions work: $(3, 4)$, $(3, 6)$ and $(5, 6)$. In each of them the kept letters spell na, and every other letter is crossed out.