피보나치 수(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) 는 다음과 같이 정의된다.

• F0 = 0
• F1 = 1
• Fi = Fi-1 + Fi-2 for i>1

Fn 을 2^m 으로 나눈 나머지를 구하는 문제이다. (단 , 0 <= n <= 2 147 483 647 과 0 <= m <= 20 )

입력

출력

입력의 끝은 EOF이다

입출력 예

입력

11 7
11 6

출력

89
25

출처: http://acm.uva.es/p/v102/10229.html
채점데이터:pl0892029