## DMOPC '14 Contest 5 P6 - Nia and Dominoes

View as PDF

Points: 20 (partial)
Time limit: 4.5s
Memory limit: 32M

Author:
Problem type

While she was living in the Spiral King's castle, Nia had lots of free time. One day, she decided to pass the time by building a very, very long line of dominoes.

A typical domino has dimensions , but some of Nia's dominoes are broken, and they have dimensions .

Nia wants to make a line of dominoes with dimensions . Nia has types of dominoes and types of dominoes. For each type of domino, Nia has an unlimited amount at her disposal. Dominoes need to have a fixed orientation in order to connect together in the line, so they cannot be rotated. Now Nia wonders how many possible ways she can make an line of dominoes using and dominoes. Two ways are considered different if they do not have the same number of dominoes or the domino in one way is of a different length or type than the domino in the other way (counting from the beginning, for any ).

Since this number may be large, please compute it modulo .

#### Input Specification

The first line of input will have , , and .

The second line of input will have .

Warning: The input is extremely large (up to 100MB). Please be careful with input methods (i.e. use the fastest possible input method your language supports). Take special note that the memory limit for this problem is 32MB. It is not guaranteed that a language slower than C/C++ can score full marks.

#### Output Specification

Output the answer on a single line.

#### Sample Input 1

1 1 101
9

#### Sample Output 1

55

#### Sample Input 2

0 1 101
1337

#### Sample Output 2

0

#### Sample Input 3

1 0 101
2015

#### Sample Output 3

1

#### Sample Input 4

2 0 10007
1234567890

#### Sample Output 4

9823

#### Sample Input 5

123 456 787
88888888

#### Sample Output 5

543

#### Sample Input 6

956 381 10009
705923593712956959302756329278756282035756528101747656392654937104729

#### Sample Output 6

5681

In the spirit of Tengen Toppa Gurren Lagann, we have ramped up the test data to 11 for this problem.

• commented on April 1, 2015, 1:45 p.m.

is there any way to get AC on this problem? reading 100 MB seems too much...

• commented on April 1, 2015, 2:28 p.m. edit 2

Reading 100MB is fine if you use getchar(). The time limit is 4.5s.

• commented on April 1, 2015, 3:51 p.m. edited

thanks, got ac using getchar()

• commented on April 14, 2015, 10:49 p.m. edit 10

Hi bossu, may I please inquire

Who in the friggity floppity cow dongus are you? Were you once a Thornhill Master Race L33t Programm3r? If so, please teach me. Otherwise, please teach me. Edit: I ask because your organization is listed as Thornhill S.S.

Thanks,

bobhob314 swaglordof80085

Edit 2: By the way,