A8572 | 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(3504_{7})=d((3+5+0+4)_{7})=d(15_{7})=d((1+5)_{7})=d(6_{7})=6_{7}$ . 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}$ .

The first line contains three integers $k$ , $b$ and $n$ ( $2<=k<=10^{9}$ , $0<=b<k$ , $1<=n<=10^{5}$ ).

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.

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.