Allp

Un șir de numere naturale $s_1, s_2, s_3, \dots, s_k$ se numește palindrom dacă $s_i = s_{k-i+1}$ pentru orice $i$ din intervalul $[1,k]$.

Spunem că un șir de numere naturale $s_1, s_2, s_3, \dots, s_k$ are proprietatea P dacă elementele sale pot fi reordonate astfel încât șirul rezultat să fie palindrom.

Un subșir al șirului $a_1, a_2, a_3, \dots, a_n$ este un șir de forma $a_{p_1}, a_{p_2}, a_{p_3}, \dots , a_{p_k}$ cu proprietatea că $1 \le p_1 < p_2 < \dots < p_k \le n$.

Valoarea unui șir $s_1, s_2, s_3, \dots, s_k$, notată cu $val(s_1,s_2,s_3,\dots,s_k)$, este numărul de subșiruri nevide ale șirului $s$ care au proprietatea P. Două subșiruri se consideră diferite dacă indicii selectați sunt diferiți, chiar dacă elementele sunt aceleași pe toate pozițiile.

Cerință

Se dau un șir de numere naturale $v_1, v_2, v_3, \dots, v_N$ și $Q$ întrebări de forma $(l,r)$. Pentru fiecare întrebare trebuie să aflați $val(v_l,v_{l+1},v_{l+2}, \dots,v_r)$. Deoarece această valoare poate fi foarte mare, se cere afișarea restului acesteia la împărțirea cu $998 \ 244 \ 353$.

Date de intrare

Fișierul de intrare allp.in conține pe prima linie numerele $N$ și $Q$. Următoarea linie conține $N$ numere naturale nenule, elementele șirului $v$. Următoarele $Q$ linii conțin fiecare câte două numere, $l$ și $r$, conform descrierii din enunț.

Date de ieșire

Fișierul de ieșire allp.out conține $Q$ linii, pe linia $i$ aflându-se răspunsul la cea de a $i$-a întrebare din fișierul de intrare.

Restricții și precizări

• $1 \leq N, Q \leq 10^6$
• $1 \leq v_i \leq 10^9$ pentru orice $i$ $(1 \le i \le N)$
• $1 \leq l \leq r \le N$ pentru orice întrebare

Exemplu

allp.in

6 3
1 1 2 3 2 4
1 3
3 6
1 6

allp.out

5
7
19

Explicație

Pentru prima întrebare subșirurile cu proprietatea P sunt formate din următoarele mulțimi de indici: $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,2,3\}$.
Pentru a doua întrebare subșirurile cu proprietatea P sunt formate din următoarele mulțimi de indici: $\{3\}$, $\{4\}$, $\{5\}$, $\{6\}$, $\{3,5\}$, $\{3,4,5\}$, $\{3,5,6\}$.