C. Тофу Тачибана Канаде
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тачибана Канаде очень любит Мапо Тофу. Однажды в столовой приготовили очень много самых разных тофу, но не всякое тофу — Мапо Тофу. Мапо Тофу — это достаточно острое тофу.

Каждый кусочек тофу в столовой имеет свой идентификатор — число, записанное в системе счисления с основанием m. Диапазон идентификаторов — это интервал [l, r] (l и r — числа в системе счисления с основанием m), и для каждого числа из этого диапазона существует кусочек тофу с таким идентификатором.

Чтобы определить, какое тофу Мапо Тофу, Тачибана Канаде выбрала n строк из цифр в системе счисления с основанием m и для каждой строки определила некоторое значение. Теперь Тачибана Канаде хочет посчитать для каждого кусочка тофу его значение следующим образом. Изначально значение кусочка тофу равно 0. Если какая-то из n выбранных строк встречается в идентификаторе тофу как подстрока, то значение этой строки нужно добавить к значению этого тофу. Если строка встречается в идентификаторе несколько раз, то и значение прибавляется несколько раз.

Тачибана Канаде считает, что тофу со значением не более k — это Мапо Тофу. И теперь девушка хочет знать, сколько кусочков тофу в столовой являются Мапо Тофу?

Входные данные

В первой строке записано три целых числа n, m и k (1 ≤ n ≤ 200; 2 ≤ m ≤ 20; 1 ≤ k ≤ 500), где n обозначает количество выбранных строк, m обозначает основание системы счисления, k — предельное значение для Мапо Тофу.

Во второй строке задана запись числа l. Сначала в строке записано целое число len (1 ≤ len ≤ 200), оно обозначает длину (количество цифр в m-ричной записи) числа l. Затем в строке записаны len разделенных пробелом целых чисел a1, a2, ..., alen (0 ≤ ai < m; a1 > 0), обозначающих цифры числа l в системе счисления m, цифра a1 наиболее значащая, цифра alen наименее значащая.

В третьей строке записано число r в таком же формате, как и число l. Гарантируется, что выполняется неравенство 1 ≤ l ≤ r.

В следующих n строках записаны выбранные для оценки строки из цифр. В i-й строке сначала записана i-ая строка из цифр в системе счисления по основанию m, а затем целое число vi — значение этой строки (1 ≤ vi ≤ 200). Все строки из цифр заданы почти в таком же формате, как и число l, единственное отличие состоит в том, что эти строки могут иметь лидирующие нули, которые важны для решения задачи (смотрите первый тестовый пример). Сумма длин строк из цифр не превышает 200.

Выходные данные

Выведите количество кусочков Мапо Тофу по модулю 1000000007 (109 + 7). Ответ должен быть десятичным целым числом.

Примеры
Входные данные
2 10 1
1 1
3 1 0 0
1 1 1
1 0 1
Выходные данные
97
Входные данные
2 10 12
2 5 9
6 6 3 5 4 9 7
2 0 6 1
3 6 7 2 1
Выходные данные
635439
Входные данные
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
Выходные данные
2
Примечание

В первом примере 10, 11 и 100 — единственные три кусочка тофу в отрезке [1, 100] со значением больше 1. Обратите внимание, что значение кусочка тофу 1 равно 1, а не 2, так как идентификаторы не могут содержать ведущих нулей и следовательно, не могут записываться как «01».

Во втором примере ни у одного кусочка на данном интервале нет значения больше 12.

В третьем примере 110000 и 110001 — единственные два идентификатора на данном интервале со значением не больше 6.