問題
2 つの数が紙に書かれている. 私はこの数を足そうと思った.
足し算が苦手な私には苦痛なことだったが、なんとか 1 日かけて足すことができたので、その答えを紙に書き込んだ.
だが突然やんちゃなたけしくんがやってきて、この数の一部を消しゴムで消してしまったのでわからなくなってしまった.
もう一度解こうとしたがもともと書かれていた数もわからなくなっているので、分からないことに気づいた. 仕方がないので答えが合うように適当に数字を当てはめることにした. このとき、答えが合うとは以下の条件をすべて満たすことをいう.
- 3 つの正の整数を、 A, B, C とする.
- A + B = C を満たす.
- 各番号の最初の数字は, 0 ではない. 一桁の数字についても同様である.
私はこの当てはめ方が何通りあるか気になった. 当てはめ方の数を 1,000,000,007 で割った余りで求めよ.
入力
入力は複数のデータセットからなる. データセットの数は 100 未満である. 各データセットは以下の形式で与えられる.
A B C
3 つの文字列 A, B, C が与えられる. A + B = C となる. 各文字列は 数字(0-9)か、疑問符(?) で構成される. ? は消された部分を表す. 各文字列の最初は 0 でないことが保証されている.
各文字列の長さは、1 文字以上 50 文字以下である. また与えられる 3 つの文字列の長さはすべて等しい.
データセットの終わりは 1 つの 0 で示される.
出力
各データセットについて、当てはめ方の数を 1,000,000,007 で割った余りで 1 行に出力せよ. 当てはめ方が 0 になる場合があるので注意すること.
入出力例
入力例
3?4 12? 5?6 ?2?4 5?7? ?9?2 ????? ????? ????? 0
出力例 1
2 40 200039979
1 つ目のデータ・セットの答えは以下の 2 通りである.
- 384 + 122 = 506
- 394 + 122 = 516