Изначально у нас был один массив — перестановка размера $$$n$$$ (массив размера $$$n$$$, где каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).

Мы провели $$$q$$$ операций. В ходе $$$i$$$-й операции мы сделали следующее:

• выбрали любой из имеющихся у нас массивов размера хотя бы $$$2$$$;
• разделили его на две непустых части (префикс и суффикс);
• записали два числа $$$l_i$$$ и $$$r_i$$$, где $$$l_i$$$ — максимум в левой из полученных частей, а $$$r_i$$$ — максимум в правой из полученных частей;
• удалили массив, который мы разделили, из набора массивов, которые мы можем использовать, а вместо него добавили две полученных части массива.

Например, пусть изначально у нас был массив $$$[6, 3, 4, 1, 2, 5]$$$, и мы провели следующие операции:

1. выбрали массив $$$[6, 3, 4, 1, 2, 5]$$$ и разделили его на $$$[6, 3]$$$ и $$$[4, 1, 2, 5]$$$. Затем мы записали $$$l_1 = 6$$$ и $$$r_1 = 5$$$, и в следующих операциях нам доступны массивы $$$[6, 3]$$$ и $$$[4, 1, 2, 5]$$$;
2. выбрали массив $$$[4, 1, 2, 5]$$$ и разделили его на $$$[4, 1, 2]$$$ и $$$[5]$$$. Затем мы записали $$$l_2 = 4$$$ и $$$r_2 = 5$$$, и в следующих операциях нам доступны массивы $$$[6, 3]$$$, $$$[4, 1, 2]$$$ и $$$[5]$$$;
3. выбрали массив $$$[4, 1, 2]$$$ и разделили его на $$$[4]$$$ и $$$[1, 2]$$$. Затем мы записали $$$l_3 = 4$$$ и $$$r_3 = 2$$$, и в следующих операциях нам доступны массивы $$$[6, 3]$$$, $$$[4]$$$, $$$[1, 2]$$$ и $$$[5]$$$.

Даны два целых числа $$$n$$$ и $$$q$$$, а также две последовательности $$$[l_1, l_2, \dots, l_q]$$$ и $$$[r_1, r_2, \dots, r_q]$$$. Перестановку размера $$$n$$$ назовем подходящей, если можно провести на ней $$$q$$$ операций и получить заданные последовательности $$$[l_1, l_2, \dots, l_q]$$$ и $$$[r_1, r_2, \dots, r_q]$$$.

Посчитайте количество подходящих перестановок.