|
D |
ACM
Puzzles Input: Standard Input Output: Standard Output |
|
The Association of Children Machines (ACM) is planning to build up a new type of puzzle for children. All the puzzles will have dimension (3×N) and has some or all of the following pieces. Some pieces can occur more than once. Since the puzzles made by ACM are in very high demand so many other companies have released counterfeit products which look just like puzzles made by ACM.
|
|
|
Figure 1: The 22 allowed pieces of
the puzzle. |
To prevent such counterfeit products ACM has taken up a measure which they hope will help the sellers to prevent the counterfeit products in their shop. As all puzzles are initially available in a box in a solved format and a (3×N) puzzle can have zillions of solutions for larger values of N. All the puzzles from ACM factory will have only some specific solutions when sold; they will be unique and only small fractions of all possible solutions. So it is more likely that the counterfeit products won’t have these orientations. You have to help them in the initial part: given the value of N you will have to find how many different solutions are there with the given pieces. You are not allowed to rotate the pieces while solving the puzzle but you can use any piece any number of time. Of course some of the pieces are mere rotation of another but they also cannot be rotated to make it look like the other. For example the piece with shape upside down T (the brown piece) cannot be rotated to look like a normal T (the pink piece).
|
|
Figure 2: The 26
solutions for N=5
|
Input
The input file contains several lines of input. Each line contains an integer N (0<N<2001). Here N denotes the width of the puzzle. The height of the puzzle is always 3. Input is terminated by a line containing a single zero. This line should not be processed.
Output
For each value of N produce one line of output. This line contains the serial of output followed by an integer which denotes the value (S % 1000000000000). Here S denotes the number of solutions for a (3×N) puzzle. Look at the output for sample input for details.
Sample
Input Output
for Sample Input
|
5 100 0 |
Case
1: 26 Case
2: 584039302899 |
Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman