$2^K$-Flip

경곽이는 길이 $N$인 이진 수열 $A = \left\{A_1, \, A_2, \cdots, \, A_{N}\right\}$를 발견하였다! 이진 수열이므로 수열의 각 원소는 $0$ 또는 $1$이다.

경곽이는 이 수열에 적용할 $K$개의 구간 쿼리를 가지고 있다. 각 쿼리는 정수 쌍 $(l_i, r_i)$로 주어지며, 이는 수열의 $l_i$번째 수부터 $r_i$번째 수까지인 $A_{l_i}, \, A_{l_i + 1}, \, \cdots, A_{r_i}$ 각각을 전부 반전(Flip)하는 연산을 의미한다. 다시 말해, $0$은 $1$로, $1$은 $0$으로 바뀐다.

경곽이는 각 쿼리를 수행할지 말지를 자유롭게 선택할 수 있다고 한다. 단, 쿼리의 순서는 변경할 수 없으며, 쿼리를 하나도 수행하지 않는 경우도 허용된다. 따라서, $K$개의 쿼리에 대해 총 $2^K$가지의 수행 조합이 존재하게 된다.

경곽이는 가능한 $2^K$가지의 경우에 대해, 쿼리를 적용한 후 수열에 포함된 $1$의 개수의 총합을 구하고자 한다. 경곽이를 도와, 가능한 모든 쿼리 수행 조합에 대한 $1$의 개수의 총합을 $998 \, 244 \, 353$으로 나눈 나머지를 출력하는 프로그램을 작성하라.

첫 번째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. ($1 \leq N,K \leq 100 \, 000$)

두 번째 줄에 길이 $N$인 이진 수열의 원소 $A_1, \, A_2, \, \cdots, \, A_N$이 공백으로 구분되어 주어진다. ($A_i \in \left\{ 0,1 \right\} \ (i = 1, \, 2, \, \cdots ,\, N)$)

세 번째 줄부터 총 $K$개의 줄에 걸쳐, 쿼리를 나타내는 두 정수 $l_i$, $r_i$가 공백으로 구분되어 주어진다. ($1 \leq l_i \leq r_i \leq N \ (i = 1, \,2, \, \cdots , \, K)$)

가능한 모든 $2^K$ 가지의 쿼리 수행 조합에 대해, 최종 수열에서 $1$의 개수의 총합을 $998 \, 244 \, 353$으로 나눈 값을 출력하라. $998 \, 244 \, 353$은 소수이다.