問題文

太郎くんは日本国に住んでいます。
この国では、$1$ 円玉、$5$ 円玉、$10$ 円玉、$50$ 円玉、$100$ 円玉、$500$ 円玉の $6$ 種類の硬貨が使われています。

貯金箱くんは硬貨を貯めに貯めて、$1$ 円玉も $5$ 円玉も $10$ 円玉も $50$ 円玉も $100$ 円玉も $500$ 円玉も、${10}^{20}$ 枚以上持っています。
しかし、太郎くんが $M$ 円のお買い物したかったのです。
太郎くんは、貯金箱くんに合計でちょうど $M$ 円分の硬貨をくれるように頼みました。
貯金箱くんは、せっかく貯めた硬貨をあげるのを渋り、問題に答えられたらあげることにしました。
貯金箱くんは、「僕が $M$ 円をあげるために渡さなければいけない最小の硬貨の枚数は何枚？」という問題を出しましたが太郎くんは一瞬で答えてしまいました。
そこで、もう $1$ 問、貯金箱くんは、「僕が $M$ 円をあげるために硬貨を渡す方法は何通り？」という問題に切り替えました。
今度は太郎君が困ってしまいました。
あなたは、貯金箱くんが $M$ 円を太郎くんに渡す方法のパターン数を ${10}^9+9$ で割った余りを求めるプログラムを書いて下さい。

入力

$T$
$M_1$
$M_2$
$⋮$
$M_T$

$1\le T\le 10000$ はテストケースの数を表す。
$1\le M_k\le {10}^{18}$ は各テストケースにおける $M$ の値を表す。

出力

出力の $k$ 行目では貯金箱くんが $M_k$ 円を太郎くんに渡す方法のパターン数を ${10}^9+9$ で割った余りを出力して下さい。

サンプル

4
10
100
1000000000
1000000000000000000

4
159
248167937
266325766