34976번 - 2ドル^K$-Flip 2 (Hard)

문제

경곽이는 길이 $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$가지의 수행 조합이 존재하게 된다.

최종적인 수열 $A^\prime = \left(A^\prime_1, ,円 A^\prime_2, \cdots, ,円 A^\prime_{N}\right)$의 점수는 모든 수가 1ドル$인 연속 부분 수열의 개수이다. 예를 들어, 수열 $\left(1, ,円 1, ,円 0, ,円 1, ,円 1, ,円 1\right)$은 아래와 같이 총 9ドル$개의 모두 1ドル$인 연속 부분 수열이 존재하므로 점수는 9ドル$이다.

• $[1, ,円 1], ,円 [2, ,円 2], ,円 [4, ,円 4], ,円 [5, ,円 5], ,円 [6, ,円 6]$
• $[1, ,円 2], ,円 [4, ,円 5], ,円 [5, ,円 6]$
• $[4, ,円 6]$

경곽이는 가능한 2ドル^K$가지의 경우에 대해, 쿼리를 적용한 후 수열의 점수의 총합을 구하고자 한다. 이를 998ドル ,円 244 ,円 353$으로 나눈 나머지를 구해보자. 998ドル ,円 244 ,円 353$은 소수다.

입력

첫 번째 줄에 수열의 길이 $N$과 쿼리의 개수 $K$가 공백으로 구분되어 주어진다. (1ドル \leq N, ,円 K < 8 ,円 192$)

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

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

출력

첫 번째 줄에 점수의 총합을 998ドル ,円 244 ,円 353$으로 나눈 나머지를 출력하라.

제한

노트