Background

Description

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

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

Format

Input

Output

Samples

30

29324
67

10

2378
17

60

13237
117

Limitation

1s, 1024KiB for each test case.