За свою долгую карьеру Андрей завоевал довольно много наград по программированию. Он считал себя действительно успешным программистом, но, к сожалению, он ничего не знал про алгоритм бинарного поиска. Прочитав уйму литературы, Андрей понял, что этот алгоритм позволяет довольно быстро найти в массиве некоторое число $$$x$$$. Для некоторого массива $$$a$$$, который нумеруются с нуля, и числа $$$x$$$ псевдокод алгоритма выглядит следующим образом:

Обратите внимание, что в описанном выше алгоритме массив нумеруется с нуля, а деление является целочисленным (с округлением вниз).

В книге, которую читал Андрей, было написано, что для корректной работы алгоритма массив обязательно должен быть отсортированным. Андрей не понял причину этого, ведь существуют неотсортированные массивы, для которых данный алгоритм найдёт число $$$x$$$.

Перед тем, как написать официальное письмо авторам книги, Андрею нужно проанализировать количество перестановок длины $$$n$$$, для которых данный алгоритм найдёт число $$$x$$$. Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке.

Помогите Андрею и выведите количество перестановок длины $$$n$$$, в которых число $$$x$$$ находится на позиции $$$pos$$$ и для которых алгоритм бинарного поиска найдёт число $$$x$$$ (вернёт true). Так как данное число может быть слишком большим, выведите остаток от деления этого числа на $$$10^9+7$$$.