Сізде ұзындығы \(n\) болатын \(a\) массиві бар, бастапқыда оның барлық элементтері нөлге тең. Сізге келесі түрдегі \(q\) сұранысын орындауға рұқсат етіледі:

Әрбір \(i\)-ші сұраныс үшін массивтің \(l_i\)-ден \(r_i\)-ге дейінгі (қоса алғанда) барлық элементтеріне XOR бірлікпен (\(\oplus\) \(1\)) операциясын қолдану қажет.

Сіздің мақсатыңыз — осы сұраныстардың кез келген қосымша жиынын (бос жиынды қоса алғанда) қолдану арқылы алынуы мүмкін әртүрлі массивтердің санын табу. Нәтижені \(998244353\) модулімен шығару керек.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(q\) (\(1 \leq n, q \leq 10^6\)) берілген.

Келесі \(q\) жолда әрбір сұраныс үшін екі бүтін сан \(l_i\) және \(r_i\) (\(1 \leq l_i \leq r_i \leq n\)) берілген, олар \(i\)-ші сұраныс қолданылатын аралықты анықтайды.

Шығару

Бір бүтін санды шығарыңыз — есептің жауабын \(998244353\) модулімен.

Мысалдар

Енгізу 1

3 2
1 3
2 2

Жауап 1

4

Ескертпелер

Бастапқы массив: \([0, 0, 0]\)

Кез келген сұраныстар жиынын таңдау арқылы алуға болатын әртүрлі массивтер:

\(`[0, 0, 0]`\) (сұраныстарды қолданбау)

\(`[1, 1, 1]`\) (тек бірінші сұранысты қолдану)

\(`[1, 0, 1]`\) (тек екінші сұранысты қолдану)

\(`[0, 1, 0]`\) (екі сұранысты да қолдану)

Жауап: \(4\) (әртүрлі массив күйі).