Вам дана перестановка \(a_1,a_2,\ldots,a_n\) чисел от \(0\) до \(n - 1\). Вам нужно посчитать количество перестановок \(b_1,b_2,\ldots,b_n\), похожих на перестановку \(a\).
Две перестановки \(a\) и \(b\) размера \(n\) называются похожими, если для всех отрезков \([l,r]\) (\(1 \le l \le r \le n\)) выполняется следующее условие: \(\)\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),\(\) где \(\operatorname{MEX}\) набора чисел \(c_1,c_2,\ldots,c_k\) определяется как наименьшее неотрицательное целое число \(x\), которое не встречается в наборе чисел \(c\). Например, \(\operatorname{MEX}([1,2,3,4,5])=0\), а \(\operatorname{MEX}([0,1,2,4,5])=3\).
Так как количество таких перестановок может быть очень большим, вам нужно вывести его остаток по модулю \(10^9+7\).
В этой задаче перестановкой размера \(n\) является массив, состоящий из \(n\) различных целых чисел от \(0\) до \(n-1\) в произвольном порядке. Например, \([1,0,2,4,3]\) является перестановкой, а \([0,1,1]\) не является, так как \(1\) встречается в массиве дважды. \([0,1,3]\) также не является перестановкой, так как \(n=3\) и в массиве есть число \(3\).
Примечание
В первом наборе входных данных единственными перестановками, похожими на \(a=[4,0,3,2,1]\), являются \([4,0,3,2,1]\) и \([4,0,2,3,1]\).
Во втором и третьем наборах входных данных только данные перестановки похожи на себя.
В четвёртом наборе входных данных есть \(4\) перестановки, похожие на \(a=[1,2,4,0,5,3]\):
- \([1,2,4,0,5,3]\);
- \([1,2,5,0,4,3]\);
- \([1,4,2,0,5,3]\);
- \([1,5,2,0,4,3]\).