Привезли новые рабочие столы, и нужно с ними поскорее разобраться, так как в офисе стало очень тесно! Вам нужно составить новую рассадку инженеров в офисе. Столы пронумерованы, и вы провели опрос среди инженеров, выяснив, за каким столом они работают сейчас, и за каким столом они хотели бы работать (может совпадать с тем столом, за которым они сейчас работают). Каждый инженер должен либо остаться на своем месте, либо переместиться на то место, которое он обозначил как желаемое. Никакие два инженера не работают сейчас за одним столом, и после пересадки никакие два инженера также не должны работать за одним столом.
Сколько существует способов рассадить инженеров так, чтобы удовлетворить описанным ограничениям? Ответ может быть большим, поэтому выведите его по модулю 1000000007 = 109 + 7.
Выходные данные
Выведите число способов рассадить всех инженеров по модулю 1000000007 = 109 + 7.
Примечание
Следующие рассадки возможны в первом примере:
- 1 5 3 7
- 1 2 3 7
- 5 2 3 7
- 1 5 7 3
- 1 2 7 3
- 5 2 7 3
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 5
5 2
3 7
7 3
|
6
|
|
2
|
5
1 10
2 10
3 10
4 10
5 5
|
5
|