Problem D
Number Anagrams

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 $2031$ 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 $1234$ 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 $1234$.

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 $1234$.

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 $1000000007$. 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^{\text{th}}$ number is generated using the following formula: $X_i=(a\cdot X_{i-1}+b)modc$. $X_1=d$.

Input

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.

Output

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.

Example

The numbers that would be generated in the example are $1,5,17,53,61,85,57,73,21,65$.

Limits

• $1\le N\le 100000$

• $1\le M\le 1000$

• $1\le a,b,d<c\le 100000$

• All starting numbers $S_i$ will be numbers that Tom has seen during the day.

10 2
3 2 100 1
1
5

3
4