Background

Mrnaoketong搬新家了（不是）

Description

Mrnaoketong要买木地板来铺，可是只有$1*1$和$2*2$两种规格的，因为Mrnaoketrong手头拮据，所以必须恰好把地面铺满而且还不能切割买来的木地板，这个时候Mrnaoketong想起来要出周赛题，所以正好考考你，当我的新家（没有）地面是一个$N*3$的矩形时，一共有多少种方案摆放木地板

Input

一个正整数N<=1000

Output

方案数取余12190116

Samples

5

21

Limitation

1s, 1024KiB for each test case.