Each Digit Comparison 2

2 secs 1024 MB
Raclamusi

問題文


桁の整数 があります。
シミュラ君は の大小を比べようとしましたが、 桁以上ある数を比べるのがとても嫌いです。
そこで、各桁ごとに数の大小を判断し、長さ の文字列 を作ることにしました。
について、 の左から 番目の桁をそれぞれ としたとき、 なら < なら > なら = です。

である整数 が与えられます。
このとき、考えられる の値は何通りありますか。 で割った余りで答えてください。

制約


  • は整数である。
  • < , > , = のいずれかである。
  • によって考えられる の値が必ず存在する。

入力


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



出力


答えを出力ください。

入出力例


入力例1
3
936
=<>
出力例1
9

通りです。


入力例2
5
12345
==><<
出力例2
60

入力例3
10
2718281828
==========
出力例3
1

入力例4
30
888888888888888888888888888888
=><=><=><=><=><=><=><=><=><=><
出力例4
75497471

で割った余りを出力してください。

提出


Go (1.14)