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

Any string of length has 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 *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 has distinct subsequences, and that the one appears times. Then the *repetitivity* of is defined as . For example, the repetitivity of `zoo`

is

#### Input Specification

Each test case contains a line containing the string (with length at most ), followed by a line containing a single integer . You may assume that only contains characters with ASCII codes between and inclusive (these are all printable, non-whitespace characters).

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

#### Output Specification

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

#### Sample Input 1

```
zoo
10
```

#### Output for Sample Input 1

`2`

#### Sample Input 2

```
@#$%
1000000
```

#### Output for Sample Input 2

`16`

## Comments

Is it a special privilage for Java?

Refer to this.

whoever wrote up this problem forgot to define M, the original version states: "The output should consist of a single line, containing the repetitivity of S, modulo M"

Fixed.