#P1140. Mrnaoketong的新家

Mrnaoketong的新家

Background

Mrnaoketong搬新家了(不是)

Description

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

Input

一个正整数N<=1000

Output

方案数取余12190116

Samples

5
21

Limitation

1s, 1024KiB for each test case.