Назовем блоком в бинарной строке (строке, состоящей из символов 0 и/или 1) ее непрерывную подстроку из символов одного и того же типа, которую нельзя продлить ни влево, ни вправо. Например, в строке 110001111 три блока:

• 11 (с $$$1$$$-го символа по $$$2$$$-й символ);
• 000 (с $$$3$$$-го символа по $$$5$$$-й символ);
• 1111 (с $$$6$$$-го символа по $$$9$$$-й символ).

Подстрока с $$$7$$$-го символа по $$$9$$$-й символ 111 не является блоком, потому что ее можно продлить влево. Подстрока с $$$1$$$-го символа по $$$5$$$-й символ 11000 не является блоком, потому что она содержит символы разных типов.

Назовем строку красивой, если из нее можно удалить ровно один блок так, чтобы получилась строка из нечетного количества блоков. Например:

• строка 110001111 красивая, потому что можно удалить блок с $$$3$$$-го по $$$5$$$-й символ, и получится строка 111111, состоящая из одного блока;
• строка 1010 красивая, потому что можно удалить блок с $$$1$$$-го по $$$1$$$-й символ, и получится строка 010, состоящая из трех блоков;
• строка 0000 некрасивая, потому что единственный способ удалить из нее блок приведет к тому, что мы получим пустую строку, а она состоит из $$$0$$$ блоков.

Дано число $$$n$$$ и $$$m$$$ ограничений, $$$i$$$-е из которых описывается парой целых чисел $$$l_i, r_i$$$. Обозначим за $$$s[l:r]$$$ подстроку строки $$$s$$$ с символа $$$l$$$ по символ $$$r$$$ включительно, то есть $$$s[l:r] = s_l s_{l+1} \dots s_r$$$. Ваша задача — посчитать количество бинарных строк $$$s$$$ длины $$$n$$$, удовлетворяющих следующему условию:

• для каждого $$$i$$$ от $$$1$$$ до $$$m$$$ подстрока $$$s[l_i:r_i]$$$ является красивой.