問題文
N 桁の整数 A,B があります。
まがお君は A,B の大小を比べようとしましたが、頭が悪くて 2 桁以上ある数の大小がわかりません。
そこで、各桁ごとに数の大小を判断し、長さ N の文字列 S を作ることにしました。 1≤i≤N について、 A,B の左から i 番目の桁をそれぞれ Ai,Bi としたとき、 Si は Ai<Bi なら <
、 Ai>Bi なら >
、 Ai=Bi なら =
です。
C=min(A,B) である整数 C が与えられます。
このとき、考えられる max(A,B) の値は何通りありますか。109+7 で割った余りで答えてください。
制約
- 2≤N≤105
- 10N−1≤C<10N
- N,C は整数である。
- Si は
<
, >
, =
のいずれかである。
- C と S によって考えられる max(A,B) の値が必ず存在する。
入力
入力は以下の形式で与えられます。
出力
答えを出力ください。
入出力例
709,719,729,809,819,829,909,919,929 の 9 通りです。
入力例3
10
3141592653
==========
入力例4
30
100000000000000000000000000000
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
109+7 で割った余りを出力してください。