Problem Statement

Define the function $f(X)$ as follows.
$f(X) = \left\{ \begin{array}{ll} X & (X < 10) \\ f(Xの桁和) & (10 \le X)\end{array} \right.$
An integer sequence $A$ with $N$ elements that satisfies the following conditions is called a "beautiful sequence".

• For all $i(1 \le i \le N)$, $10^{L_i} \le A_i < 10^{R_i}$ or $A_i = 0$
• For all $i(1 \le i \le N)$, $f(f(A_1) + f(A_2) + \dots + f(A_i)) = D_i$

Constraints

• $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$ are integers

Input

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

The first line contains the integer $N$.
The second line contains the integer sequence $L$, separated by spaces.
The third line contains the integer sequence $R$, separated by spaces.
The fourth line contains the integer sequence $D$, separated by spaces.

Output

Output the total number of "beautiful sequences", modulo $10^9+7$.
Print a newline at the end.

Sample

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