No.41 貯金箱の溜息(EASY)
問題
太郎くんは六並び国に住んでいます。
この国では、\(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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。