Tom is really interested in numbers, so he decided to become an accountant. To his great pleasure, he gets to see lots of numbers every day in his new job. Even though it is exciting to see all these numbers, the actual work happens to be boring. In order to combat boredom, he has created a game to help him have fun with all the interesting numbers.
From all the numbers he sees during a day, he picks one. Then he adds a digit, and rearranges the digits so that they form another number he has seen during the day. For example, $123$ can be turned into $2\, 031$ by adding a $0$ and rearranging the digits. He keeps doing this with the new number until he has created a number that cannot be transformed into one he has seen using this method.
Letś say that he has seen the numbers $2$, $32$, $322$, $243$, and $1\, 234$ during the day. If he starts with $2$, he can produce $32$ next. Then he can choose between $322$ and $243$. If he chooses $322$, the game is over, since he cannot create new numbers from there. If he chooses $243$ instead, he can have one more turn, creating $1\, 234$.
Tom likes long numbers, so he tries to make the numbers with the largest number of digits possible. In the example above, he would choose to make $234$ as his second move, so that he would be able to make $1\, 234$.
Help Tom find out how many ways he can make numbers with the largest number of digits possible, for a given list of $M$ starting numbers. The results can be very large, so you should output them modulo $1\, 000\, 000\, 007$. Note that Tom is only interested in the length of the number, so if several numbers are longest, count the ways to make all of them. Note that transforming $55$ to $555$ only counts as one way of making $555$, not three. If Tom sees the same number twice in a day, it still only counts as one number.
Since Tom sees a lot of numbers every day, we will use a Pseudo Random Number Generator to generate the numbers. The $i^\textrm {th}$ number is generated using the following formula: $X_ i = (a \cdot X_{i-1} + b) \bmod c$. $X_1 = d$.
The first line of the input consists of two space-separated
integers $N$ and
$M$, indicating how many
numbers to generate, and how many starting numbers you need to
process.
The second line of the input consists of four space-separated
integers $a$, $b$, $c$, $d$, describing the pseudo random
number generator.
The next $M$ lines each
contain a single integer $S_
i$, describing a starting number that you should
process.
For each of the $M$ starting numbers, output a line with a single integer, representing the number of ways he can make the longest possible numbers for that starting number.
The numbers that would be generated in the example are $1, 5, 17, 53, 61, 85, 57, 73, 21, 65$.
$1 \leq N \leq 100\, 000$
$1 \leq M \leq 1\, 000$
$1 \leq a, b, d < c \leq 100\, 000$
All starting numbers $S_ i$ will be numbers that Tom has seen during the day.
Sample Input 1 | Sample Output 1 |
---|---|
10 2 3 2 100 1 1 5 |
3 4 |