## DMOPC '14 Contest 6 P5 - Planning

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M

Author:
Problem type

After hearing all the wonderful things about the TTC subway, you are finally splurging \$11.50 (that's an hour's pay!) on a day pass so you can spend your beautiful sunny Saturday "Riding the Rocket" in dark tunnels. This calls for some planning!

You have a map, which looks like four equilateral "triangles" glued together (you're terrible at drawing triangles, so you draw squares that look like a triangle when glued together instead).

Your map ends up looking like something below (the triangles have "side length" in this case).

With this map, you have effectively divided Toronto into square-shaped sectors! You know the subway system of Toronto has two very special properties — all subway lines cross exactly one edge between two square-shaped sectors! Also, each sector belongs to exactly one subway line. Therefore, there are two sectors joined by an edge in a single subway line.

You don't know the exact layout of the subway lines, and you're too lazy to go online and search it up. Therefore, you have adopted the foolproof strategy of drawing out all possible subway configurations for a map made up of equilateral triangles of side length . Two configurations are different if any two sectors are joined by a subway line in one configuration, but they are not in the other. How many configurations do you have to draw? Since this number may be very large, output it modulo (, a prime number).

#### Sample Input

1

#### Sample Output

2

#### Explanation of Output for Sample Input

The two possible subway configurations (subway lines numbered for your convenience, same number indicates part of the same line):

  1         1
1   2     2   1
2         2

• commented on April 7, 2015, 5:48 p.m.

Why is

2

2 1

1

for the sample case not valid?

• commented on April 7, 2015, 5:55 p.m.

because it's the same thing as the first in the sample output

• commented on April 7, 2015, 5:41 p.m.

Are subway lines allowed to stop without reaching the other end of the map?

• commented on April 7, 2015, 6:07 p.m.

Subway lines only consist of two "adjacent" squares.

• commented on April 7, 2015, 6:19 p.m.

So you can't have them span >3 squares?

• commented on April 7, 2015, 6:25 p.m.

Nope.

• commented on April 7, 2015, 5:15 p.m.

With this map, you have effectively divided Toronto into square-shaped sectors

Are the sectors the big thing(approximation of a square), or the individual "pixels" of the triangles?

• commented on April 7, 2015, 5:16 p.m.

The "pixels".