Problem I: 11224111122411

腕が引っかかって抜けない。

机の裏に転がり込んでしまったものを拾おうとして、懐中電灯代わりに携帯の画面で照らしながら腕を挿し込んでみたが、うっかり何かに引っかかって抜けなくなってしまった。無理に動かすと痛い。

どうしよう。どうすれば脱出できるのだろう。大声で助けを呼ぶか。恥ずかしいので却下したいが、独力で脱出するのは難しそうだ。いや、声の届く範囲には誰もいなかったはずだ。焦る気持ちを押さえて辺りを見渡す。あのパソコンに手が届けばメールで助けを呼べるのだが、あいにく遠すぎる。やはり偶然誰かが通りかかるのを待つしかないのか。

いや待て、メールを送る機械ならあるじゃないか。手の届くところというよりも、既にこの手の中に。深く伸ばした手の先の画面はぼやけてよく見えないが、長年使っている携帯だ。画面が見えなくてもメールぐらいは送れるはずだ。

慎重に、頭の中に画面を描きながらボタンを押す。指の感触だけを頼りに、タイプミスだけはしないように、数字キーを何度も押してメッセージを打ち込む。漢字変換はしない、平仮名でもきっと伝わるはずだ。つくづくタッチパネルが主流のスマートフォンに乗り換えていなくてよかったと思う。

深呼吸をして、送信ボタンに指をかける。しばらくして、携帯が軽く震えた。送信完了の合図だ。溜息。しばらくすれば友人が助けに来るに違いない。

友人は賢いので適切に解釈してくれると思うのだが、今送ったメッセージは、本当に送りたかったメッセージとは違うものになっているかもしれない。この携帯の文字入力メソッドは広く使われているものと同じで、例えば「あ」行の平仮名を入力するのに "1" のボタンを使う。 "1" は「あ」を、 "11" は「い」を、以下同様に "11111" が「お」を表す。平仮名はループする、つまり "111111" もまた「あ」となる。「か」行は "2" 、「さ」行は "3" 、 ... を使い、同じボタンを続けて押したときの挙動は "1" の例と同様である。

ただし、この文字入力メソッドにはちょっと厄介な挙動がある。数字ボタンを押した後しばらく操作しないでいると、平仮名への変換が強制的に行われてしまうのだ。つまり、３回続けて "1" を押せば 「う」 になるが、時間を置いて３回 "1" を押すと「あああ」になる。別の例をあげると、 "111111" と押したとき、その押す間隔によって入力された文字列は「あ」にも「ああああああ」にもなる。"111111111111"は「い」かもしれないし、「ええいああ」かもしれないし、１２個の「あ」になるかもしれない。なお、違う数字ボタンを押したときにも平仮名への変換はおこなわれるので、 "12345" は「あかさたな」という文字列にしかなりえない。

さて、慎重にタイプしたので間違ったボタンを押したつもりはないのだが、適切な間隔でボタンを押せた自信はない。本当に送りたかったメッセージとは違うものを送ってしまった可能性は大いにあるのだ。さて、送られたかもしれない文字列の数は何通りだろうか。ああ、これは友人が助けに来るまでの暇つぶしにいいかもしれない。遅くても５時間以内に助けに来てくれるだろう。それまでに解けるといいのだけど。

Input

入力は複数のケースからなる。
各ケースは以下のフォーマットで与えられる。 

string

入力の終わりは,入力が"#"からなる行によって与えられる

string は0から9の間の数字を最大100,000個含む。
string の長さが10,000を越える入力は50個を超えない。

テストケースのファイルサイズは5MB以下であることが保証される。
またテストケースの数は100を超えない。

各数字キーで入力可能な文字は以下の表のとおりである。

数字 入力可能な文字
1 あいうえお
2 かきくけこ
3 さしすせそ
4 たちつてと
5 なにぬねの
6 はひふへほ
7 まみむめも
8 やゆよ
9 らりるれろ
0 わをん

Output

文章の解釈の仕方を100000007で割った余りを1行に出力せよ。

Sample input

1
11
111111
111111111111
12345
11111111119999999999
11111111113333333333
11111111118888888888
11111111112222222222111111111
11111111110000000000444444444
11224111122411
888888888888999999999999888888888888999999999999999999
666666666666666777333333333338888888888
1111114444441111111444499999931111111222222222222888111111115555
#

Sample output

1
2
32
1856
1
230400
230400
156480
56217600
38181120
128
26681431
61684293
40046720

The University of Aizu Programming Contest 2011 Summer
原案: Tomoya Sakai
問題文: Takashi Tayama