Problems
In how many ways can you tile a 4 × N (1 ≤ N ≤ 109) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo 105.
Input
Input consists of several test cases followed by a line containing 0. Each test case consists of a single integer N, respectively.
Output
For each test case, output the answer modulo 105.
Example
1
3
5
0
1
11
95
Source
POJ Monthly Contest, poj 3420
You must sign in to write code.