時間制限 : sec, メモリ制限 : KB
Japanese

D: Many Decimal Integers

問題

数字 (0 から 9) のみからなる文字列 S と、数字 と ? のみからなる文字列 T が与えられます。ST は同じ長さです。

T 内に存在するそれぞれの ? について、0 から 9 までの数字のいずれか 1 つに変更し、数字のみからなる文字列 T' を作ることを考えます。このとき、f(T') \leq f(S) である必要があります。ここで f(t) は、文字列 t10 進数として読んだときの整数値を返す関数とします。 また、T' の最上位の桁にある数字は 0 であってもよいものとします。

あり得る文字列 T' すべてについて、f(T') の値の総和を 10^9+7 で割った余りを求めてください。なお、条件を満たす T' がひとつも存在しない場合は 0 と答えてください。

入力形式

S
T

制約

  • 1 \leq |S| = |T| \leq 2 \times 10^5
  • S は数字 (0 から 9) のみからなる文字列
  • T は数字と ? のみからなる文字列

出力形式

条件を満たす T' の総和を 10^9+7 で割った余りを一行に出力してください。

入力例1

73
6?

出力例1

645

T' としてあり得る文字列は、60 から 69 までの 10 通りあります。これらの合計は 645 です。

入力例2

42
?1

出力例2

105

T' の最上位の桁にある数字は 0 でもよいため、01 も条件を満たします。

入力例3

1730597319
16??35??8?

出力例3

502295105

10^9 + 7 で割った余りを求めてください。