橘奏非常喜欢麻婆豆腐。有一天,食堂煮了各种各样的豆腐来卖,但并不是所有的豆腐都是麻婆豆腐,只有那些足够辣的才能称为麻婆豆腐。
食堂里的每块豆腐都有一个基于 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 的二进制数。