### 2013 Canadian Computing Competition, Stage 2

## Day 2, Problem 3: 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

, andzoo

appear only once, - the empty subsequence appears only once,
- and the subsequences
o

andzo

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 . For example, the repetitivity of

zoois

1^{2} + 1^{2} + 1^{2}
+ 1^{2} + 2^{2} + 2^{2} = 12.

### Input

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 ≤ `M` ≤ 10^{9}). You
may assume that `S` only contains characters with ASCII codes between
33 and 126 inclusive (these are all printable, nonwhitespace characters).

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

### Output

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

### Sample Input 1

zoo 10

### Sample Output 1

2

### Sample Input 2

@#$% 1000000

### Sample Output 2

16

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 10.00s

**Memory Limit:** 512M

**Added:** May 19, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...