시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 3 | 3 | 3 | 100.000% |
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:
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
12 + 12 + 12 + 12 + 22 + 22 = 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\).
zoo 10
2
@#$% 1000000
16