CF216E.Martian Luck

You know that the Martians use a number system with base k. Digit b (0 ≤ b < k) is considered lucky, as the first contact between the Martians and the Earthlings occurred in year b (by Martian chronology).

A digital root d(x) of number x is a number that consists of a single digit, resulting after cascading summing of all digits of number x. Word "cascading" means that if the first summing gives us a number that consists of several digits, then we sum up all digits again, and again, until we get a one digit number.

For example, d(35047) = d((3 + 5 + 0 + 4)7) = d(157) = d((1 + 5)7) = d(67) = 67. In this sample the calculations are performed in the 7-base notation.

If a number's digital root equals b, the Martians also call this number lucky.

You have string s, which consists of n digits in the k-base notation system. Your task is to find, how many distinct substrings of the given string are lucky numbers. Leading zeroes are permitted in the numbers.

Note that substring s[i... j] of the string s = _a_1_a_2... a__n (1 ≤ i ≤ j ≤ n) is the string a__i__a__i + 1... a__j. Two substrings s[_i_1... _j_1] and s[_i_2... _j_2] of the string s are different if either _i_1 ≠ _i_2 or _j_1 ≠ _j_2.

你知道火星人使用以 $k$ 为底的进制数系统。数字 $b$（其中 $0 \leq b < k$）被视为幸运数字，因为火星人与地球人的首次接触发生在火星历的第 $b$ 年。

一个数 $x$ 的数字根 $d(x)$ 是指将 $x$ 的所有数位反复相加，直至结果为一位数后所得的数。“反复”意味着：若第一次求和得到的数仍含多位数字，则需继续对其各位数字求和，如此反复，直到结果为一位数为止。

例如，$d(35047) = d((3 + 5 + 0 + 4)_7) = d(15_7) = d((1 + 5)_7) = d(6_7) = 6_7$。本例中所有计算均在七进制下进行。

若一个数的数字根等于 $b$，火星人也将该数称为幸运数。

现给你一个字符串 $s$，它由 $n$ 个 $k$ 进制数字组成。你的任务是：找出该字符串中有多少个互不相同的子串是幸运数。允许子串带前导零。

注意：字符串 $s = a_1a_2\ldots a_n$（其中 $1 \leq i \leq j \leq n$）的子串 $s[i\ldots j]$ 定义为字符串 $a_i a_{i+1} \ldots a_j$。字符串 $s$ 的两个子串 $s[i_1\ldots j_1]$ 和 $s[i_2\ldots j_2]$ 被视为不同，当且仅当 $i_1 \ne i_2$ 或 $j_1 \ne j_2$。

The first line contains three integers k, b and n (2 ≤ k ≤ 109, 0 ≤ b < k, 1 ≤ n ≤ 105).

The second line contains string s as a sequence of n integers, representing digits in the k-base notation: the i-th integer equals a__i (0 ≤ a__i < k) — the i-th digit of string s. The numbers in the lines are space-separated.

第一行包含三个整数 $k$、$b$ 和 $n$（$2 \leq k \leq 10^9$，$0 \leq b < k$，$1 \leq n \leq 10^5$）。

第二行包含字符串 $s$，以 $n$ 个整数的序列形式给出，表示 $k$ 进制下的各位数字：第 $i$ 个整数等于 $a_i$（$0 \leq a_i < k$），即字符串 $s$ 的第 $i$ 位数字。行中的数字以空格分隔。

Print a single integer — the number of substrings that are lucky numbers.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出一个整数——幸运数字子串的个数。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first sample the following substrings have the sought digital root: s[1... 2] = "3 2", s[1... 3] = "3 2 0", s[3... 4] = "0 5", s[4... 4] = "5" and s[2... 6] = "2 0 5 6 1".

在第一个样例中，以下子串具有所求的数字根：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"。