사다리

면접 대비

시간 제한1초메모리 제한128 MB

요약

한 칸이나 두 칸씩 s개 발판을 올라 정상에 도달하는 경우의 수를 구하고 각 질의마다 2^p로 나눈 나머지를 출력합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

Bajtek이 사다리를 오릅니다. 한 걸음에 한 칸 위로 오르거나 두 칸 위로 오를 수 있습니다. 사다리의 꼭대기, 즉 마지막 칸까지 오르는 서로 다른 방법이 몇 가지인지 구하려고 합니다.

방법의 수가 매우 커질 수 있으므로, 그 수를 $2^p$ 으로 나눈 나머지만 구합니다.

입력

첫 번째 줄에 데이터 집합의 개수를 나타내는 정수 $z$ (1 ≤ $z$ ≤ $10^6$ )가 주어집니다. 이어지는 $z$ 개의 각 줄에는 두 정수 $s$ , $p$ (1 ≤ $s$ ≤ $10^6$ , 1 ≤ $p$ ≤ 30)가 주어지며, 각각 사다리의 칸 수와 문제에서의 값 $p$ 를 의미합니다.

출력

각 데이터 집합마다 사다리 꼭대기에 도달하는 방법의 수를 $2^p$ 으로 나눈 나머지를 한 줄에 하나씩 출력합니다.

예제1

예제 1
입력
```
5
3 2
3 1
4 2
1 1
2 1
```
예상 출력
```
3
1
1
1
0
```