Description

菲波那契数大家可能都已经很熟悉了： f(1)=0； f(2)=1； f(n)=f(n-1)+f(n-2) n>2。 因此，当需要其除以某个数的余数时，不妨加一些处理就可以得到。

Input

输入数据为一些整数对P、K，P(1<P<5000)，表示菲波那契数的序号，K(1<=K<15)表示2的幂次方。遇到两个空格隔开的0时表示结束处理。

Output

输出其第P个菲波那契数除以2的K次方的余数。

Sample

Input

6 2
20 10
0 0

Output

1
85