問題文

関数$f(X)$を次のように定義します。
$f(X) = \left\{ \begin{array}{ll} X & (X < 10) \\ f(Xの桁和) & (10 \le X)\end{array} \right.$
次の条件を満たす要素数$N$の整数列$A$を「美しい数列」と定義します。

• 全ての$i(1 \le i \le N)$について、$10^{L_i} \le A_i < 10^{R_i}$ または $A_i = 0$
• 全ての$i(1 \le i \le N)$について、$f(f(A_1) + f(A_2) + \dots + f(A_i)) = D_i$

制約

• $1 \le N \le 10^5$
• $0 \le L_i < R_i \le 10^{18}$
• $0 \le D_i \le 9$
• $N, L_i, R_i, D_i$は整数

入力

$N$
$L_1 \ L_2 \dots L_N$
$R_1 \ R_2 \dots R_N$
$D_1 \ D_2 \dots D_N$

1行目には整数$N$が入力されます。
2行目には整数列$L$が空白区切りで入力されます。
3行目には整数列$R$が空白区切りで入力されます。
4行目には整数列$D$が空白区切りで入力されます。

出力

「美しい数列」の総数を$10^9+7$で割ったあまりを出力してください。
最後に改行してください。

サンプル

2
0 1
1 2
3 4

10

5
8 13 21 34 55
89 144 233 377 610
1 1 2 3 5

880448910