Conveyor Label Residue Pair Count

A parcel-sorting conveyor stamps every barcode with a string of lowercase letters, one character per station along the belt. For quality control, the system tracks a running weight as the barcode passes: each letter contributes a value equal to its position in the alphabet ('a' = 1, 'b' = 2, ..., 'z' = 26), and the running weight after station i (for i = 1..n, where n is the barcode's length) is the sum of the letter values of the first i characters — that is, the weight of the length-i prefix of the barcode.

For inspection purposes every prefix is reduced to a residue class by taking its running weight modulo a fixed inspection modulus m. Two prefixes (of possibly different lengths) are called linked if they fall into the same residue class.

Count the number of unordered pairs of prefixes, out of all n prefixes of the barcode, that are linked.

Input format

Line 1: a string s of lowercase English letters (the barcode). Line 2: a single integer m (the inspection modulus).

Output format

A single integer: the number of unordered pairs of prefixes of s that share the same residue modulo m.

Constraints

1 <= length of s <= 100000 1 <= m <= 100000 Every character of s is a lowercase English letter ('a'-'z').

ab
3

0

aab
2

1