6762번 - Repetitivity 출처다국어

Any string of length \(n\) has \(2^n\) subsequences, which are the strings obtained by deleting some subset of the characters. But these subsequences may not all be distinct. For example, the string “zoo” has only 6 distinct subsequences:

• the subsequences “z”, “oo”, and “zoo” appear only once,
• the empty subsequence appears only once,
• and the subsequences “o” and “zo” each appear twice.

Suppose a string \(S\) has \(k\) distinct subsequences, and that the \(i\)th one appears \(f_i\) times. Then the repetitivity of \(S\) is defined as \(\sum_{i=1}^{k}{f_i^2}\). For example, the repetitivity of “zoo” is

1² + 1² + 1² + 1² + 2² + 2² = 12.

Each test case contains a line containing the string \(S\) (with length at most 10 000), followed by a line containing a single integer \(M\) (\(2 \le M \le 1 000 000 000\)). You may assume that \(S\) only contains characters with ASCII codes between 33 and 126 inclusive (these are all printable, nonwhitespace characters).

The output should consist of a single line, containing the repetitivity of \(S\), modulo \(M\).