Background

Description

Pell数列1,2,3,…a1,a2,a3,… 的定义

给出一个正整数n（1<=n<=35如：n=30时），试求 Pell 数列的第k 项模上32767是多少。

Format

Input

Output

Samples

30

3038
1664079

10

2378
109

Limitation

1s, 1024KiB for each test case.