Safe Teddy Bear Arrangements

Byteoian is a company specialized in producing children’s toys. They are well known for the high quality of their products. Recently, however, it was discovered that their teddy bears have a fatal flaw. There are four models of teddy bears: \(A1\), \(A2\), \(B1\), and \(B2\). When any three teddy bears sharing the same letter (i.e. A or B) or the same digit (i.e. 1 or 2) are placed consecutively, the bears are fatally damaged.

A placement is considered safe if there is no contiguous subsequence of three bears that have either all the same letter or all the same digit.

Given an integer \(n\) representing the number of teddy bears you have collected, determine the number of safe arrangements in which you can place these bears. Since the answer can be large, output it modulo \(1\,000\,000\) (i.e. \(10^6\)).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^5\) or as specified) on one line, representing the number of teddy bears.

outputFormat

Output a single integer: the number of safe arrangements of teddy bears modulo \(1\,000\,000\).

sample

1

4