Canadian Computing Competition: 2013 Stage 2, Day 2, Problem 3

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^\text{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

$$\displaystyle 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12$$

Input Specification

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 10^9)~. You may assume that ~S~ only contains characters with ASCII codes between ~33~ and ~126~ inclusive (these are all printable, non-whitespace characters).

For test cases worth ~20\%~ of the points, you may assume that ~S~ will be at most ~20~ characters long.

Output Specification

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

Sample Input 1

zoo
10

Output for Sample Input 1

2

Sample Input 2

@#$%
1000000

Output for Sample Input 2

16