8672번 - Drabina 다국어

문제

Bajtek wchodzi na drabinę. Może on jednym krokiem wejść jeden szczebelek wyżej lub dwa szczebelki wyżej. Zastanawiamy się, na ile różnych sposobów może on wejść na szczyt (ostatni szczebelek) drabiny.

Liczba tych sposobów może być bardzo duża, więc interesuje nas tylko reszta z dzielenia przez liczbę 2^p.

입력

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą z (1 ≤ z ≤ 10⁶), oznaczającą liczbę zestawów danych. Kolejnych z wierszy zawiera po dwie liczby całkowite s, p (1 ≤ s ≤ 10⁶, 1 ≤ p ≤ 30), oznaczające odpowiednio liczbę szczebelków drabiny i wartość p z treści zadania.

출력

Dla każdego zestawu danych powinna się znaleźć w nowej linii jedna liczba całkowita, równa liczbie sposobów dojścia na szczyt drabiny modulo (reszta z dzielenia) 2^p.

제한

힌트