Description

已知菲波那契(简写为Fib)函数对于正整数构成一个数列。 f(0)=1,f(1)=1,f(n)=f(n-1)+f(n-2)。（n>1） 2的幂次方有2，4，8，…，第n项Fib数对于2的幂次方的余数是多少，是你现在要关心的问题。

Input

输入数据有若干整数对，每对整数m,n表示2的m(1≤m≤32)次幂和第n(0<n<400000)项Fib数。

Output

对于每对整数m,n，输出第n项Fib数对于2的m次方的余数。

Sample

Input

2 2
2 3
5 28

Output

2
3
21

Source: qianneng