Изначально у нас был один массив — перестановка размера \(n\) (массив размера \(n\), где каждое целое число от \(1\) до \(n\) встречается ровно один раз).
Мы провели \(q\) операций. В ходе \(i\)-й операции мы сделали следующее:
- выбрали любой из имеющихся у нас массивов размера хотя бы \(2\);
- разделили его на две непустых части (префикс и суффикс);
- записали два числа \(l_i\) и \(r_i\), где \(l_i\) — максимум в левой из полученных частей, а \(r_i\) — максимум в правой из полученных частей;
- удалили массив, который мы разделили, из набора массивов, которые мы можем использовать, а вместо него добавили две полученных части массива.
Например, пусть изначально у нас был массив \([6, 3, 4, 1, 2, 5]\), и мы провели следующие операции:
- выбрали массив \([6, 3, 4, 1, 2, 5]\) и разделили его на \([6, 3]\) и \([4, 1, 2, 5]\). Затем мы записали \(l_1 = 6\) и \(r_1 = 5\), и в следующих операциях нам доступны массивы \([6, 3]\) и \([4, 1, 2, 5]\);
- выбрали массив \([4, 1, 2, 5]\) и разделили его на \([4, 1, 2]\) и \([5]\). Затем мы записали \(l_2 = 4\) и \(r_2 = 5\), и в следующих операциях нам доступны массивы \([6, 3]\), \([4, 1, 2]\) и \([5]\);
- выбрали массив \([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]\).
Посчитайте количество подходящих перестановок.