За свою долгую карьеру Андрей завоевал довольно много наград по программированию. Он считал себя действительно успешным программистом, но, к сожалению, он ничего не знал про алгоритм бинарного поиска. Прочитав уйму литературы, Андрей понял, что этот алгоритм позволяет довольно быстро найти в массиве некоторое число \(x\). Для некоторого массива \(a\), который нумеруются с нуля, и числа \(x\) псевдокод алгоритма выглядит следующим образом:
Обратите внимание, что в описанном выше алгоритме массив нумеруется с нуля, а деление является целочисленным (с округлением вниз).
В книге, которую читал Андрей, было написано, что для корректной работы алгоритма массив обязательно должен быть отсортированным. Андрей не понял причину этого, ведь существуют неотсортированные массивы, для которых данный алгоритм найдёт число \(x\).
Перед тем, как написать официальное письмо авторам книги, Андрею нужно проанализировать количество перестановок длины \(n\), для которых данный алгоритм найдёт число \(x\). Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке.
Помогите Андрею и выведите количество перестановок длины \(n\), в которых число \(x\) находится на позиции \(pos\) и для которых алгоритм бинарного поиска найдёт число \(x\) (вернёт true). Так как данное число может быть слишком большим, выведите остаток от деления этого числа на \(10^9+7\).
Примечание
Все подходящие перестановки в первом тестовом примере: \((2, 3, 1, 4)\), \((2, 4, 1, 3)\), \((3, 2, 1, 4)\), \((3, 4, 1, 2)\), \((4, 2, 1, 3)\), \((4, 3, 1, 2)\).