题目描述

给定一个 B 进制下、恰好有 N 位的数：

$$c = \overline{c_{N-1}c_{N-2}\dots c_1c_0}$$

已知：

$$c = a + b$$

其中 a 和 b 也是 B 进制下恰好 N 位的数，即：

$$a = \overline{a_{N-1}a_{N-2}\dots a_1a_0}, \qquad b = \overline{b_{N-1}b_{N-2}\dots b_1b_0}$$

并且这三个数都没有前导零。

另外还给出 M 条限制，每条限制为以下两种之一：

• a_i + b_j = k
• a_i - b_j = k

其中 k 的值可以因限制不同而不同。

请编写程序 digits.cpp，求满足以下条件的有序数对 (a, b) 的个数：

• 所有 M 条限制都成立；
• a + b = c。

由于答案可能很大，你需要输出它对 10^9 + 7 取模后的结果。如果不存在合法数对，则答案为 0。

输入格式

第一行输入三个整数 N, M, B，分别表示：

• 每个数的位数；
• 限制条数；
• 进制。

第二行输入和 c 的各位数字，用空格分隔，按从高位到低位顺序给出，即：

$$c_{N-1}, c_{N-2}, \dots, c_0$$

接下来 M 行，每行一条限制，格式为：

• i + j k，表示 a_i + b_j = k；
• i - j k，表示 a_i - b_j = k。

输出格式

输出一个整数，表示满足条件的合法数对 (a, b) 的个数，结果对 10^9 + 7 取模。

限制

• 1 ≤ N ≤ 18
• 0 ≤ M ≤ 70
• 2 ≤ B ≤ 10^7
• 0 ≤ a_i, b_i, c_i < B
• -B < k < 2 × B - 1
• 三个数都恰好有 N 位，即：

$$a_{N-1}, b_{N-1}, c_{N-1} \ne 0$$

子任务与评分

子任务	分值	N ≤	B	额外限制
1	7	18	≤ 30	M = 0
2	8	6	= 10	-
3	20	18	≤ 30	对所有 0 ≤ i < N，都有 c_i = B - 1
4	13		≤ 100	所有限制都只涉及形如 a_i 与 b_i 的同下标数字对
5	18		≤ 30	所有限制都形如 a_i + b_j = k（即没有减法限制）
6	11			-
7	23		≤ 10^7

样例

输入 1

5 4 20
10 10 10 12 10
3 + 1 10
4 + 1 10
4 - 4 0
0 + 2 10

输出 1

11

输入 2

2 2 20
10 10
1 + 0 12
1 - 0 0

输出 2

1

输入 3

2 1 20
10 10
1 + 0 12

输出 3

9

输入 4

3 1 20
8 10 10
0 - 0 -2

输出 4

261

输入 5

3 1 20
10 10 8
0 - 0 -2

输出 5

341

样例解释

为方便描述，下文把 B 进制下、各位为 a_k, ..., a_1, a_0 的数记作：

[a_k, ..., a_1, a_0]

对于第 1 组样例，合法数对共有 11 个：

1. [5,5,0,7,0] + [5,5,10,5,10]
2. [5,5,1,7,1] + [5,5,9,5,9]
3. [5,5,2,7,2] + [5,5,8,5,8]
4. [5,5,3,7,3] + [5,5,7,5,7]
5. [5,5,4,7,4] + [5,5,6,5,6]
6. [5,5,5,7,5] + [5,5,5,5,5]
7. [5,5,6,7,6] + [5,5,4,5,4]
8. [5,5,7,7,7] + [5,5,3,5,3]
9. [5,5,8,7,8] + [5,5,2,5,2]
10. [5,5,9,7,9] + [5,5,1,5,1]
11. [5,5,10,7,10] + [5,5,0,5,0]

对于第 2 组样例，唯一合法数对为：

1. [6,4] + [4,6]

对于第 3 组样例，合法数对共有 9 个：

1. [2,0] + [8,10]
2. [3,1] + [7,9]
3. [4,2] + [6,8]
4. [5,3] + [5,7]
5. [6,4] + [4,6]
6. [7,5] + [3,5]
7. [8,6] + [2,4]
8. [9,7] + [1,3]
9. [1,19] + [8,11]