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 $10000$), 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\mathrm{\%}$ 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