$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$은 소수이다.