furnica

Se consideră un arbore binar complet cu $T$ niveluri. Nodurile sunt numerotate cu numere naturale începând de la $1$, astfel încât nodul $X$ are doi fii: $2 \cdot X$ și $2 \cdot X + 1$. Astfel, avem următoarea structură:

O furnică aflată în nodul $X$ poate face un pas folosind una dintre următoarele $4$ reguli:

1. Dacă $X > 1$, furnica poate urca în părintele lui $X$ (egal cu $\lfloor X / 2 \rfloor$).
2. Dacă $X < 2^{T-1}$, furnica poate coborî în fiul stâng al lui $X$ (egal cu $2 \cdot X$, par).
3. Dacă $X < 2^{T-1}$, furnica poate coborî în fiul drept al lui $X$ (egal cu $2 \cdot X + 1$, impar).
4. Dacă $X > 1$, furnica poate trece la fratele lui $X$ (egal cu $X \oplus 1$).

Notă: prin $\oplus$ se înțelege operația sau-exclusiv (XOR) pe biți, reprezentată în C/C++ prin operatorul ^.

Se dau $Q$ întrebări, fiecare reprezentată prin două numere $N$ și $K$, cu semnificația: „Câte drumuri distincte formate din exact $K$ pași de furnică există de la nodul $1$ la nodul $N$?”

Un drum este reprezentat printr-un șir de lungime $K$ cu valori între $1$ și $4$, în care fiecare valoare indică tipul pasului făcut, în ordine. Toți pașii trebuie să fie legali în momentul efectuării lor (de exemplu, din rădăcină nu se poate urca la părinte, iar dintr-o frunză nu se poate coborî la fii). De exemplu, dacă $T \geq 3$, un drum valid de la nodul $1$ la nodul $2$ de lungime $4$ poate fi reprezentat de șirul $[2, 3, 4, 1]$, iar nodurile parcurse sunt $1 \to 2 \to 5 \to 4 \to 2$.

Două drumuri sunt considerate distincte dacă șirurile care le reprezintă diferă în cel puțin o poziție (sau, echivalent, dacă șirurile de noduri parcurse, în ordine, diferă în cel puțin o poziție).

Cerință

Se cere să se afișeze răspunsul pentru fiecare întrebare, în ordinea în care acestea au fost date. Deoarece acestea pot fi foarte mari, se vor afișa modulo $998244353$.

Date de intrare

Pe prima linie a fișierului de intrare furnica.in se află numerele naturale $T$ și $Q$, în această ordine. Pe fiecare dintre următoarele $Q$ linii se află câte două numere naturale $N$ și $K$, în această ordine, descriind o întrebare.

Date de ieșire

În fișierul de ieșire furnica.out se vor afișa $Q$ linii; pe linia $i$ se va găsi răspunsul la întrebarea $i$ (modulo $998244353$), în ordinea în care întrebările au fost citite.

Restricții și precizări

• $1 \leq T \leq 60$
• $1 \leq Q \leq 1 \ 000$
• $1 \leq N \leq 2^T - 1$
• $1 \leq K \leq 10^{18}$

Exemplu

furnica.in

3 4
2 1
1 2
4 2
2 4

furnica.out

1
2
1
11

Explicație

Arborele are $T = 3$ niveluri, deci nodurile sunt $1$, $2$, $\dots$, $7$, iar frunzele sunt $\{4, 5, 6, 7\}$.

• $N = 2$, $K = 1$: singurul drum de un pas de la $1$ la $2$ este $[2]$ (coborârea pe fiul stâng), deci răspunsul este $1$.
• $N = 1$, $K = 2$: pentru a reveni în rădăcină în doi pași, furnica trebuie să coboare la un fiu și apoi să urce înapoi: $[2, 1]$ ($1 \to 2 \to 1$) și $[3, 1]$ ($1 \to 3 \to 1$), deci răspunsul este $2$.
• $N = 4$, $K = 2$: singura posibilitate este $[2, 2]$ ($1 \to 2 \to 4$), deci răspunsul este $1$.
• $N = 2$, $K = 4$: există $11$ drumuri distincte de lungime $4$ care pornesc din nodul $1$ și se termină în nodul $2$ (unul dintre ele fiind $[2, 3, 4, 1]$ din exemplul de mai sus).