CF433E.Tachibana Kanade's Tofu

Tachibana Kanade likes Mapo Tofu very much. One day, the canteen cooked all kinds of tofu to sell, but not all tofu is Mapo Tofu, only those spicy enough can be called Mapo Tofu.

Each piece of tofu in the canteen is given a m-based number, all numbers are in the range [l, r] (l and r being m-based numbers), and for every m-based integer in the range [l, r], there exists a piece of tofu with that number.

To judge what tofu is Mapo Tofu, Tachibana Kanade chose n m-based number strings, and assigned a value to each string. If a string appears in the number of a tofu, the value of the string will be added to the value of that tofu. If a string appears multiple times, then the value is also added that many times. Initially the value of each tofu is zero.

Tachibana Kanade considers tofu with values no more than k to be Mapo Tofu. So now Tachibana Kanade wants to know, how many pieces of tofu are Mapo Tofu?

橘佳奈非常喜欢麻婆豆腐。一天，食堂烹制了各种豆腐来售卖，但并非所有豆腐都是麻婆豆腐，只有那些足够辣的豆腐才能被称为麻婆豆腐。

食堂中的每块豆腐都被赋予一个 $m$ 进制数，所有这些数均在区间 $[l,\,r]$ 内（其中 $l$ 和 $r$ 均为 $m$ 进制数），且对区间 $[l,\,r]$ 内的每一个 $m$ 进制整数，都恰好存在一块编号为此数的豆腐。

为了判断哪些豆腐是麻婆豆腐，橘佳奈选定了 $n$ 个 $m$ 进制数字串，并为每个数字串赋予一个权值。若某数字串在某块豆腐的编号中出现，则该数字串的权值将被加到这块豆腐的总权值上；若该数字串在编号中出现多次，则其权值也将被累加相应次数。每块豆腐的初始权值均为零。

橘佳奈将总权值不超过 $k$ 的豆腐视为麻婆豆腐。那么现在她想知道：共有多少块豆腐是麻婆豆腐？

The first line contains three integers n, m and k (1 ≤ n ≤ 200; 2 ≤ m ≤ 20; 1 ≤ k ≤ 500). Where n denotes the number of strings, m denotes the base used, and k denotes the limit of the value for Mapo Tofu.

The second line represents the number l. The first integer in the line is len (1 ≤ len ≤ 200), describing the length (number of digits in base m) of l. Then follow len integers _a_1, _a_2, ..., a__len (0 ≤ a__i < m; _a_1 > 0) separated by spaces, representing the digits of l, with _a_1 being the highest digit and a__len being the lowest digit.

The third line represents the number r in the same format as l. It is guaranteed that 1 ≤ l ≤ r.

Then follow n lines, each line describing a number string. The i-th line contains the i-th number string and v__i — the value of the i-th string (1 ≤ v__i ≤ 200). All number strings are described in almost the same format as l, the only difference is number strings may contain necessary leading zeros (see the first example). The sum of the lengths of all number strings does not exceed 200.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n ≤ 200$；$2 ≤ m ≤ 20$；$1 ≤ k ≤ 500$）。其中 $n$ 表示字符串的数量，$m$ 表示所用的进制，$k$ 表示麻婆豆腐的数值上限。

第二行表示数字 $l$。该行第一个整数为 $len$（$1 ≤ len ≤ 200$），描述 $l$ 的长度（即其在 $m$ 进制下的位数）。随后是 $len$ 个整数 $a_1,\,a_2,\,...,\,a_{len}$（$0 ≤ a_i < m$；$a_1 > 0$），以空格分隔，表示 $l$ 的各位数字，其中 $a_1$ 为最高位，$a_{len}$ 为最低位。

第三行以与 $l$ 相同的格式表示数字 $r$。保证 $1 ≤ l ≤ r$。

接下来是 $n$ 行，每行描述一个数字字符串。第 $i$ 行包含第 $i$ 个数字字符串及其对应的值 $v_i$（$1 ≤ v_i ≤ 200$）。所有数字字符串均以与 $l$ 几乎相同的格式描述，唯一区别在于数字字符串可能包含必要的前导零（参见第一个样例）。所有数字字符串的总长度不超过 $200$。

Output the number of pieces of Mapo Tofu modulo 1000000007 (109 + 7). The answer should be a decimal integer.

输出麻婆豆腐块数对 1000000007（$10^9 + 7$）取模的结果。答案应为一个十进制整数。

In the first sample, 10, 11 and 100 are the only three decimal numbers in [1, 100] with a value greater than 1. Here the value of 1 is 1 but not 2, since numbers cannot contain leading zeros and thus cannot be written as "01".

In the second sample, no numbers in the given interval have a value greater than 12.

In the third sample, 110000 and 110001 are the only two binary numbers in the given interval with a value no greater than 6.

在第一个样例中，10、11 和 100 是区间 [1, 100] 中仅有的三个十进制数，其“值”大于 1。此处 1 的“值”为 1 而非 2，因为数字不能包含前导零，因此不能写作 "01"。

在第二个样例中，给定区间内没有任何数的“值”大于 12。

在第三个样例中，110000 和 110001 是给定区间内仅有的两个二进制数，其“值”不大于 6。