一个整数如果仅由“好”数字组成，则被称为好数。

给你 $N$ 个区间 $[L_i, R_i]$ 以及一个被认为是“好”数字的数字集合。请计算有多少种方法可以从每个区间中各选择一个整数，使得它们的和是一个好数。你可以在不同的区间中选择相同的数字。如果存在一个整数 $i$ ($1 \le i \le N$)，使得从区间 $i$ 中选择的整数不同，则认为两种方法是不同的。由于答案可能很大，请输出其对 $10^9 + 7$ 取模后的结果。

输入格式

输入的第一行包含十个整数：其中第 $i$ 个整数（从 $0$ 到 $9$ 编号）在数字 $i$ 是“好”数字时为 $1$，否则为 $0$。

第二行包含一个整数 $N$ ($1 \le N \le 7$)，表示区间的数量。

接下来的 $N$ 行，每行包含两个没有前导零的整数：$L_i$ 和 $R_i$ ($0 \le L_i \le R_i < 10^{10}$)。

输出格式

输出方法数对 $10^9 + 7$ 取模后的结果。

样例

输入样例 1

1 1 1 1 1 1 1 1 1 1
2
4 6
15 19

输出样例 1

15

输入样例 2

1 0 1 0 1 0 1 0 0 0
2
4 6
15 19

输出样例 2

7

输入样例 3

1 0 0 1 1 1 1 1 1 1
2
4 6
15 19

输出样例 3

0