Как известно, марсиане пользуются системой счисления с основанием 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.
Выходные данные
Выведите единственное целое число — количество подстрок, которые являются счастливыми числами.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере искомый цифровой корень имеют подстроки 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».