909 . Tiling
Description
Use the following tiles:
to tile a floor of size 5*n.
Given n, how many ways are there to do so?
Input Format
The first line contain an integer T, indicating the number of testcases.
In the next T line each describe one testcase. Each line has a single integer N, indicating the the size of the floor is 5*N.
Output Format
For each N, output an integer on a single line: the number of ways mod 123456789.
1 <= N <= 1015
1 <= T <= 15
Sample Input 1
2 3 4
Sample Output 1
62 0
Hints
Problem Source
Migrated from old NTUJ.
Mathematika'09
Subtasks
| No. | Testdata Range | Score |
|---|