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

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

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

#样例1#
##样例输入1##

6 2
20 10
0 0

##样例输出1##

1
85

#限制#
1000ms
32768KB

#提示#

#来源#