409362: GYM103491 D Cipher 5-1-15-10 and 3-1-15-10

D. Шифр 5-1-15-10 и 3-1-15-10ограничение по времени на тест1.5 секундограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Берляндия и Кекляндия посылают к друг другу дипломатов с сообщениями. Чтобы никто не смог перехватить послание, они решили шифровать свои сообщения так: вместо букв они выписывают через пробел цифры номера букв в алфавите, в котором A букв, начиная с 1 в k-ичной системе исчисления (цифры каждого числа тоже через пробел). Однако, иногда по дороге цифры смазываются и нельзя понять, что там было. Однажды правительству Кекляндии пришло очередное сообщение, но в нем было очень много пропусков. На всякий случай они решили подсчитать, сколькими способами можно восстановить сообщение (составить такое сообщение, чтобы после шифровки получилась эта же последовательности цифр, не считая стертых цифр), ведь тогда будет слишком сложно понять, что хотела сообщить Берляндия. Сообщение может быть очень длинным, поэтому Кекляндия попросила вас автоматизировать этот процесс и сообщать результат по модулю $$$10^9 + 7$$$.

Помогите Кекляндии подсчитать количество способов восстановить сообщение!

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

В первой строке вводятся три числа $$$n$$$, $$$A$$$ и $$$k$$$ - размер полученного Кекляндией сообщения, размер алфавита и основание системы исчисления, использованная для перевода букв в цифры, соответсвенно.

Во второй строке вводится полученное Кекляндией сообщение. Цифры переведены в десятичную систему исчисления. Если вместо натурального числа стоит -1, значит цифра на этом месте стерлась.

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

В единственной строке выведите одно число – ответ на задачу.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Вам будет показан только вердикт на первом непройденном тесте в группе.

№	Баллы	Ограничения	Необходимые подзадачи
1	3	$$$1 \leq n, A \leq 10^3, k=10,$$$ все $$$a_i=-1$$$
2	4	$$$1 \leq n, A \leq 10^3, 2 \leq k \leq 1000,$$$ все $$$a_i=-1$$$	1
3	6	$$$1 \leq n \leq 10^5, 1 \leq A \leq 10^{9}, 2 \leq k \leq 10^9,$$$ все $$$a_i=-1$$$	1,2
4	3	$$$1 \leq n, A \leq 10^3, k=10,$$$ все $$$a_i \neq -1$$$
5	3	$$$1 \leq n, A \leq 10^3, 2 \leq k \leq 1000,$$$ все $$$a_i \neq -1$$$	4
6	2	$$$1 \leq n \leq 10^5, 1 \leq A \leq 10^{9}, k=10,$$$ все $$$a_i \neq -1$$$	4
7	3	$$$1 \leq n \leq 10^5, 1 \leq A \leq 10^{9}, 2 \leq k \leq 10^9,$$$ все $$$a_i \neq -1$$$	4,5,6
8	9	$$$1 \leq n \leq 5, A=26, k=10$$$
9	3	$$$1 \leq n, A \leq 10^3, k=10$$$	1,4,8
10	8	$$$1 \leq n, A \leq 10^3, 2 \leq k \leq 1000$$$	1,2,4,5,8,9
11	16	$$$1 \leq n \leq 10^5, 1 \leq A \leq 10^{9}, k=10$$$	1,4,6,8,9
12	11	$$$1 \leq n \leq 10^5, 1 \leq A \leq 10^{9}, 2 \leq k \leq 10^9$$$	1-11
13	17	$$$1 \leq n \leq 5 \cdot 10^5, 1 \leq A \leq 10^{18}, k=10$$$	1,4,6,8,9,11
14	12	$$$1 \leq n \leq 5 \cdot 10^5, 1 \leq A \leq 10^{18}, 2 \leq k \leq 10^{18}$$$	1-13

ПримерыВходные данные

3 26 12
-1 6 2

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

12

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

2 26 10
7 4

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

1

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

4 26 10
-1 -1 -1 -1

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

10981

Примечание

Даже если все цифры остались, то сообщение не всегда можно восстановить единственным образом.