Problem Statement

Taro lives in Japan.
In this country, \(6\) types of coins are used: \(1\)-yen, \(5\)-yen, \(10\)-yen, \(50\)-yen, \(100\)-yen, and \(500\)-yen coins.

Piggy Bank has saved up coins over and over, and has at least \(10^{20}\) coins of each type: \(1\)-yen, \(5\)-yen, \(10\)-yen, \(50\)-yen, \(100\)-yen, and \(500\)-yen coins.
However, Taro wanted to go shopping for \(M\) yen.
Taro asked Piggy Bank to give him coins totaling exactly \(M\) yen.
Reluctant to give away the coins he had worked so hard to save, Piggy Bank decided to give them only if Taro could answer a question.
Piggy Bank asked, "What is the minimum number of coins I must hand over to give you \(M\) yen?", but Taro answered instantly.
So, with \(1\) more question, Piggy Bank switched to this one: "How many ways are there for me to hand over coins to give you \(M\) yen?"
This time, Taro was stuck.
Write a program that finds the number of ways Piggy Bank can give \(M\) yen to Taro, modulo \(10^9+9\).

Input

\(T\)
\(M_1\)
\(M_2\)
\(\vdots\)
\(M_T\)

\(1 \leq T \leq 10000\) represents the number of test cases.
\(1 \leq M_k \leq 10^{18}\) represents the value of \(M\) in each test case.

Output

On the \(k\)-th line of the output, print the number of ways Piggy Bank can give \(M_k\) yen to Taro, modulo \(10^9+9\).

Sample

4
10
100
1000000000
1000000000000000000

4
159
248167937
266325766