사다리

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

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

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

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