No.41 貯金箱の溜息(EASY)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 124
作問者 : LayCurseLayCurse
2 ProblemId : 40 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:48:21

問題

太郎くんは六並び国に住んでいます。
この国では、\(1\) 円玉のほか、\(6\) つの数字からなるゾロ目、つまり、\(111111\) 円玉、\(222222\) 円玉、…、\(999999\) 円玉の、合計 \(10\) 種類の硬貨が使われています。

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

入力

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

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

出力

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

サンプル

サンプル1
入力
7
1
111112
222222
10000000
100000000
1000000000
10000000000
出力
1
2
4
21312056
818664350
50564368
385490639

\(1\) 円を渡す方法は \(1\) 円玉を \(1\) つ渡す以外に方法はありません。
\(111112\) 円を渡す方法は \(1\) 円玉を \(111112\) 枚渡す、\(111111\) 円玉と \(1\) 円玉を \(1\) 枚ずつ渡すの \(2\) 通りの方法があります。
\(10^{10}\) は \(2^{32}\) より大きいことに注意してください。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。