E. Счастье для марсиан
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, марсиане пользуются системой счисления с основанием k. Цифра b (0 ≤ b < k) считается счастливой, поскольку именно в b-ом году (по марсианскому летоисчислению) произошел первый контакт марсиан с землянами.

Цифровым корнем d(x) числа x называется число, состоящее из одной цифры, которое получается после каскадного сложения всех цифр числа x. Слово «каскадный» означает, что если после первого сложения получилось число из нескольких цифр, то все цифры складываются вновь, и так далее, пока не получится число из одной цифры.

Например, d(35047) = d((3 + 5 + 0 + 4)7) = d(157) = d((1 + 5)7) = d(67) = 67. В данном примере вычисления производятся в системе счисления с основанием 7.

Число, цифровой корень которого равен b, марсиане также называют счастливым.

Имеется строка s, состоящая из n цифр в k-ичной системе счисления. Требуется найти количество различных подстрок данной строки, которые являются счастливыми числами. Лидирующие нули в числах разрешаются.

Напомним, что подстрокой s[i... j] строки s = a1a2... an (1 ≤ i ≤ j ≤ n) является строка aiai + 1... aj. Две подстроки s[i1... j1] и s[i2... j2] строки s считаются различными, если либо i1 ≠ i2, либо j1 ≠ j2.

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

В первой строке записаны три целых числа k, b и n (2 ≤ k ≤ 109, 0 ≤ b < k, 1 ≤ n ≤ 105).

Во второй строке записана строка s в виде последовательности из n целых чисел, обозначающих цифры в k-ичной системе счисления: i-ое из этих чисел равно ai (0 ≤ ai < k) — i-ая цифра строки s. Числа в строках разделяются пробелами.

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

Выведите единственное целое число — количество подстрок, которые являются счастливыми числами.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
10 5 6
3 2 0 5 6 1
Выходные данные
5
Входные данные
7 6 4
3 5 0 4
Выходные данные
1
Входные данные
257 0 3
0 0 256
Выходные данные
3
Примечание

В первом примере искомый цифровой корень имеют подстроки s[1... 2] = «3 2», s[1... 3] = «3 2 0», s[3... 4] = «0 5», s[4... 4] = «5» и s[2... 6] = «2 0 5 6 1».