시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3735115196534.391%

문제

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라. 

입력

첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어진다.

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

제한

  • 1 ≤ P ≤ 10,000
  • 1 ≤ Q ≤ 2,000,000,000

예제 입력 1

10
5 10
6 25
10 21
32 43
100 100
50 50
25 25
45 67
109 32
128 128

예제 출력 1

Case #1: 5
Case #2: 8
Case #3: 13
Case #4: 15
Case #5: 75
Case #6: 25
Case #7: 0
Case #8: 19
Case #9: 9
Case #10: 69
W3sicHJvYmxlbV9pZCI6Ijk3MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NDAmbmJzcDtcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MSwgMSwgMiwgMywgNSwgOCwgMTMsIDIxLCAzNCwgLi4uPFwvcD5cclxuXHJcbjxwPlx1YWMwMSZuYnNwO1x1YzIyYlx1Yzc5MFx1YjI5NCZuYnNwO1x1YzU1ZVx1Yzc1OCBcdWI0NTAgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5QXHVjNjQwIFEgXHVhZGY4XHViOWFjXHVhY2UwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgUFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwXHViOTdjJm5ic3A7UVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHViNzdjXHVjNzc4XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBUXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4MTVcdWMyMTggUFx1YzY0MCBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCZuYnNwOyZxdW90O0Nhc2UgI3g6IE0mcXVvdDsgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+eFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOCgxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MSksIE1cdWM3NDAgUFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwXHViOTdjIFFcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IFAgJmxlOyAxMCwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFEgJmxlOyAyLDAwMCwwMDAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiI5NzExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlib25hY2NpIiwiZGVzY3JpcHRpb24iOiI8cD5EZXBpY3RlZCBiZWxvdyBpcyB0aGUgRmlib25hY2NpIHNlcXVlbmNlOjxiciBcLz5cclxuMSwgMSwgMiwgMywgNSwgOCwgMTMsIDIxLCAzNCwgLi4uPFwvcD5cclxuXHJcbjxwPkFzIHlvdSBjYW4gc2VlLCBlYWNoIHZhbHVlIGZyb20gMiBvbndhcmRzIGlzIHRoZSBzdW0gb2YgdGhlIHByZXZpb3VzIHR3byB2YWx1ZXMuIEdpdmVuIFAsIFEgYW5kIG4sIGZpbmQgdGhlIG50aCBmaWJvbmFjY2kgbnVtYmVyIG1vZHVsdXMgUS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBnaXZlcyBhbiBpbnRlZ2VyIFQsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGludGVnZXJzIFAgYW5kIFEuIFEgaXMgYmV0d2VlbiAxIGFuZCAyLDAwMCwwMDAsMDAwIGluY2x1c2l2ZS4gUCBpcyBiZXR3ZWVuIDEgYW5kIDEwLDAwMCBpbmNsdXNpdmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB0aGUgb3V0cHV0IGNvbnRhaW5zIGEgbGluZSBpbiB0aGUgZm9ybWF0IENhc2UgI3g6IE0sIHdoZXJlIHggaXMgdGhlIGNhc2UgbnVtYmVyIChzdGFydGluZyBmcm9tIDEpIGFuZCBNIGlzIHRoZSBQJnJzcXVvO3RoIGZpYm9uYWNjaSBudW1iZXIgbW9kdWx1cyBRPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Malaysia > Malaysia National Programming Contest > Al-Khawarizmi National Programming Contest 2012 I번