CF216E Martian Luck

You know that the Martians use a number system with base $ k $ . Digit $ b $ ( $ 0

The first line contains three integers $ k $ , $ b $ and $ n $ ( $ 2

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.

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".