아이들을 위한 블록

Wango는 뛰어난 수학 선생님이다. 같은 날 태어난 두 아들 Kango와 Dango가 있고, 둘은 2년 터울이다. Kango는 9살, Dango는 7살이다. 두 아들의 생일이 다시 다가오고 있다. Wango는 두 아들에게 고등 수학을 소개하려고 각자에게 Pango 보드 한 조각씩 선물하려 한다.

크기가 $n$ ($n \ge 0$)인 Pango 보드는 단위 정사각형으로 이루어진 $2 \times n$ 직사각형이다. Pango 보드는 Pango 조각으로 빈틈없이 채워야 한다. 어떤 타일링이든 허용된다. 크기 0인 보드는 존재하며 하나뿐이고, 빈 집합을 나타낸다.

Pango 조각은 네 종류이며, 각 종류는 개수 제한 없이 쓸 수 있다. 조각은 회전할 수 없다.

Wango는 크기 $N$인 보드 하나를 사서 정수 $k$ ($0 \le k \le N$)를 고르고, Kango에게 크기 $k$인 보드를, Dango에게 크기 $N-k$인 보드를 준다. 두 보드 모두 빈틈없이 채워져 있어야 한다. Wango가 선물을 나누어 줄 수 있는 방법의 수를 구하라. Dango가 받는 보드나 Kango가 받는 보드 중 하나라도 다르면 두 방법은 서로 다르다. 두 보드는 왼쪽에서 오른쪽으로 같은 타일링이면 같은 보드로 본다. 비교할 때 보드를 회전할 수 없다.

입력은 여러 개의 테스트 케이스로 이루어지며, 한 줄에 하나씩 주어진다. 각 줄에는 Wango가 사려는 보드의 크기 $N$ ($0 \le N \le 1000000000$)이 정수로 하나 주어진다. -1이 적힌 줄이 나오면 입력이 끝나며, 이 줄은 처리하지 않는다. 테스트 케이스는 최대 300개이다.

각 테스트 케이스마다 Wango가 선물을 나누어 주는 방법의 수를 10,007로 나눈 나머지를 한 줄에 출력한다.