← 返回题目列表

Codeforces · 433/E

E. 橘奏的豆腐

中文机器翻译题面 查看原题

橘奏非常喜欢麻婆豆腐。有一天,食堂煮了各种各样的豆腐来卖,但并不是所有的豆腐都是麻婆豆腐,只有那些足够辣的才能称为麻婆豆腐。

食堂里的每块豆腐都有一个基于 m 的编号,所有编号都在 [l, r] 范围内(l 和 r 是基于 m 的编号),对于 [l, r] 范围内的每个基于 m 的整数,都存在一块具有该编号的豆腐。

为了判断什么豆腐是麻婆豆腐,橘奏选择了n个基于m的数字字符串,并为每个字符串分配了一个值。如果豆腐的编号中出现字符串,则该字符串的值将添加到该豆腐的值中。如果某个字符串出现多次,则该值也会添加多次。最初,每块豆腐的价值为零。

Tachibana Kanade 认为值不超过 k 的豆腐是麻婆豆腐。那么现在橘奏想知道,麻婆豆腐有多少块豆腐?

输入

第一行包含三个整数 n、m 和 k (1 ≤ n ≤ 200;2 ≤ m ≤ 20;1 ≤ k ≤ 500)。其中n表示字符串的数量,m表示使用的基数,k表示麻婆豆腐的值的限制。

第二行代表数字l。该行中的第一个整数是 len (1 ≤ len ≤ 200),描述 l 的长度(以 m 为基数的位数)。然后跟随 len 个整数 a1, a2, ..., alen (0 ≤ ai < m; a1 > 0),以空格分隔,代表 l 的数字,其中 a1 为最高位,alen 为最低位。

第三行表示数字r,其格式与l相同。保证 1 ≤ l ≤ r。

接下来是 n 行,每行描述一个数字字符串。第 i 行包含第 i 个数字字符串和 vi — 第 i 个字符串的值 (1 ≤ vi ≤ 200)。所有数字字符串的描述格式几乎与 l 相同,唯一的区别是数字字符串可能包含必要的前导零(请参见第一个示例)。所有数字串的长度之和不超过200。

输出

输出麻婆豆腐模 1000000007 (109 + 7) 的块数。答案应该是一个十进制整数。

示例

输入 #1

2 10 1
1 1
3 1 0 0
1 1 1
1 0 1

输出 #1

97

输入 #2

2 10 12
2 5 9
6 6 3 5 4 9 7
2 0 6 1
3 6 7 2 1

输出 #2

635439

输入 #3

4 2 6
6 1 0 1 1 1 0
6 1 1 0 1 0 0
1 1 2
3 0 1 0 5
4 0 1 1 0 4
3 1 0 1 2

输出 #3

2

注意

在第一个示例中,10、11 和 100 是 [1, 100] 中唯一三个大于 1 的十进制数字。这里 1 的值为 1,但不是 2,因为数字不能包含前导零,因此不能写为“01”。

在第二个样本中,给定区间内没有数字的值大于 12。

在第三个样本中,110000 和 110001 是给定区间内唯一两个值不大于 6 的二进制数。