Big Integers

Software engineer megeve had once again run into problems while debugging mindcoding. After finally making the code compile, the website printed a warning which read 3 4. Being a talented mathematician too, megeve instantly realised that the warning message was just an abbreviation for the 4th P3 number.

If you don't already know, megeve defines a Pk number to be a number made out of multiple copies (at least one) of 10(2)k (which means 1 followed by exactly k zero digits; for example, if k = 2, then the first 3 P2 numbers are, in this order: 100(2), 100100(2) and 100100100(2)). Please note that all Pk numbers provided above are in base 2 form.

After megeve got rid of that warning, he ran the code again and it printed T more warnings (due to the some changes in the code). Now not even megeve can fix them.

Since he is also curently working on three other important programs, he needs you to write him a program which reads two numbers T and K and N more numbers a[i], and returns the base 10 form of the a[i]-th Pk number for each i. Since the answers might be too large for standard integer types, megeve only needs the remainder when dividing the answer by 666013.

Input

The first line of the input contains two (one space separated) numbers T and K (in this order). The next T lines contain a[1], a[2], ..., a[T].

Output

The output should consist of T lines, every of which should contain the answer to megeve's problem for the a[i] coresponding from the coresponding line , modulo 666013.

Constraints

1 ≤ K ≤ 102
1 ≤ T ≤ 105
1 ≤ a[i] ≤ 101000000

All these numbers are in base 10. The size of the input file is less than 50MB.

Sample

InputOutputExplanation
1 2
3
292 The 3rd P2 number is 100100100(2) = 292(10)
Questions?

Sponsors Gold