## CCO '13 P6 - Repetitivity

View as PDF

Points: 25 (partial)
Time limit: 4.5s
Memory limit: 512M

Problem type
##### 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

• commented on May 6, 2016, 3:33 p.m.

Is it a special privilage for Java?

• commented on May 6, 2016, 4:35 p.m.

Refer to this.

• commented on March 4, 2015, 7:47 p.m.

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"

• commented on March 4, 2015, 7:50 p.m.

Fixed.