Яхуб так обрадовался изобретению графов сортировки пузырьком, что он целый день сидит в офисе и выписывает перестановки. Яхубина вся извелась — ведь теперь Яхубу нет до нее дела. И вот, стоило Яхубу выйти, Яхубина зашла к нему в офис, чтобы саботировать его научную работу — и месть ее страшна.

Девушка отыскала важную для исследования Яхуба перестановку. Перестановка состояла из n различных целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ n). Найдя перестановку, она сразу же заменила некоторые элементы перестановки числами -1.

Когда Яхуб вернулся, он обнаружил, что важная перестановка испорчена. Теперь Яхуб пытается ее восстановить. К сожалению, про изначальную перестановку он запомнил только то, что в перестановке не было ни одной неподвижной точки. Неподвижная точка перестановки — это такой элемент a_k, значение которого равняется k (a_k = k).

Ваша задача — доказать Яхубу, что восстанавливать перестановку уже не стоит. Выведите количество перестановок, которые могут оказаться изначальной важной перестановкой Яхуба по модулю 1000000007 (10⁹ + 7).