Вам дано пять целых чисел \(n\), \(i\), \(j\), \(x\), и \(y\). Найдите количество битонических перестановок \(B\), чисел от \(1\) до \(n\), таких, что \(B_i=x\), и \(B_j=y\). Так как ответ может быть очень большим, выведите его по модулю \(10^9+7\).
Битоническая перестановка — это перестановка чисел, такая, что элементы перестановки сначала увеличиваются до определенного индекса \(k\), \(2 \le k \le n-1\), а затем уменьшайте до конца. Обратитесь к примечаниям для получения дополнительных разъяснений.
Примечание
Перестановка — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в любом порядке. Например, \([2,3,1,5,4]\) это перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но \(4\) встречается в массиве).
Массив из \(n \ge 3\) элементов битонический, если его элементы сначала увеличиваются до индекса \(k\), \(2 \le k \le n-1\), а затем уменьшается до конца. Например, \([2,5,8,6,1]\) это битонический массив с \(k=3\), но \([2,5,8,1,6]\) не битонический массив (элементы сначала возрастают до \(k=3\), затем убывают, а затем возрастают снова).
Битоническая перестановка — это перестановка, в которой элементы следуют вышеупомянутому битоническому свойству. Например, \([2,3,5,4,1]\) является битонической перестановкой, но \([2,3,5,1,4]\) не является битонической перестановкой (поскольку это не битонический массив) и \([2,3,4,4,1]\)также не является битонической перестановкой (поскольку это не перестановка).
Объяснение примера из условий
Для \(n=3\), возможные перестановки это \([1,2,3]\), \([1,3,2]\), \([2,1,3]\), \([2,3,1]\), \([3,1,2]\), и \([3,2,1]\). Среди приведенных перестановок битоническими перестановками являются \([1,3,2]\) и \([2,3,1]\).
В первом тестовом примере ожидаемая перестановка должна иметь вид \([2,?,3]\), который не удовлетворяет ни одной из двух битонических перестановок с \(n=3\), следовательно, ответ равен 0.
Во втором тестовом примере ожидаемая перестановка должна иметь вид \([?,3,2]\), который удовлетворяет только битонической перестановке \([1,3,2]\), следовательно, ответ 1.