Each Digit Comparison

問題文

$N$ 桁の整数 $A,B$ があります。
まがお君は $A,B$ の大小を比べようとしましたが、頭が悪くて $2$ 桁以上ある数の大小がわかりません。
そこで、各桁ごとに数の大小を判断し、長さ $N$ の文字列 $S$ を作ることにしました。 $1 \le i \le N$ について、 $A,B$ の左から $i$ 番目の桁をそれぞれ $A_i,B_i$ としたとき、 $S_i$ は $A_i \lt B_i$ なら < 、 $A_i \gt B_i$ なら > 、 $A_i = B_i$ なら = です。

$C = \min(A,B)$ である整数 $C$ が与えられます。
このとき、考えられる $\max(A,B)$ の値は何通りありますか。$10^9+7$ で割った余りで答えてください。

制約

• $2 \le N \le 10^5$
• $10^{N-1} \le C \lt 10^N$
• $N,C$ は整数である。
• $S_i$ は < , > , = のいずれかである。
• $C$ と $S$ によって考えられる $\max(A,B)$ の値が必ず存在する。

入力

入力は以下の形式で与えられます。

出力

答えを出力ください。

入出力例

3
639
<>=

9

$709,719,729,809,819,829,909,919,929$ の $9$ 通りです。

5
98765
==><<

60

10
3141592653
==========

1

30
100000000000000000000000000000
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

953555159

$10^9+7$ で割った余りを出力してください。