Counting the number of tilings of different sized boards with dominoes (i.e. 2-by-1 rectangles) can be a pretty difficult task. However, here you must only determine the number of ways to tile boards of height 3 and some width.

The input file **DATA3.txt** will contain 5 lines, each containing an integer 0 ≤ `N` ≤ 30 representing the width of the board you want to tile with dominoes.

The output file **OUT3.txt** will contain 5 lines, where each line represents the number of ways to tile a 3×`N` board with dominoes modulo 1,000,000. (i.e. The output is the remainder you get when you divide the number of ways to tile a 3×`N` board with dominoes by 10^{6}.)

Sample Input:

```
1
4
3
25
13
```

Sample Output:

```
1
36
11
952111
413351
```