Background

Description

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

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

Format

Input

Output

Samples

30

1 2 5 12 29 70 169 408 985 2378 5741 13860 694 15248 31190 12094 22611 24549 6175 4132 14439 243 14925 30093 9577 16480 9770 3253 16276 3038

10

1 2 5 12 29 70 169 408 985 2378

Limitation

1s, 1024KiB for each test case.