Expected Singing Time

In the Singing Kingdom, every person’s name is a non‐empty string consisting solely of digits from 1 to n. In this kingdom, a host of soldiers (the Gulu troops) gain strength by continuously singing the names of their leaders—the Bull Chiefs. Each singing session proceeds as follows: the soldier presses the integer generator which returns an integer uniformly at random from 1 to n, and he sings that number (taking one time unit). The singing sequence is the ordered list of sung numbers. If at any moment the singing sequence contains a chief’s name (i.e. the chief's name appears as a contiguous substring of the sequence), the singing immediately stops.

Define the following:

• Singing sequence: If a soldier sings x numbers with a_i being the number sung in the i-th unit, then the singing sequence is (a₁,a₂,…,a_x).
• Integer generator: A device that, upon pressing a button, returns an integer uniformly at random from 1 to n.
• Singing time: The total number of time units (digits) sung before the process terminates.

The expected singing time is defined as the average number of time units in one singing session (its expected value), which is guaranteed to be a non-negative integer. The people love to sing and wish the singing time to be as long as possible. With that in mind, they plan to fire some of the Bull Chiefs so that the average singing time becomes longer. However, they cannot fire all the chiefs (otherwise the singing would never stop) and decide to retain exactly one Bull Chief while dismissing the others.

Your task is: Given the integer n, the number of Bull Chiefs t, and each chief’s name, determine, for 1 ≤ i ≤ t, what the expected singing time would be if only the i-th Bull Chief is retained. Because the answer can be huge, output only the last 4 digits of the result (padding with leading zeroes if necessary).

Note: The expectation, although derived from a probabilistic process, turns out to be an exact non-negative integer.

inputFormat

The first line contains two integers n and t.

The following t lines each contain a non-empty string representing a Bull Chief’s name. Each character in the string is a digit between 1 and n (inclusive).

outputFormat

Output t lines. The i-th line should contain a 4-digit string: the last 4 digits of the expected singing time if only the i-th chief is retained. If the result has fewer than 4 digits, pad with leading zeroes.

sample

2 3
1
11
121

0002
0006
0010