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

제한

서브태스크

힌트