E. Беспорядок на рабочих местах
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Привезли новые рабочие столы, и нужно с ними поскорее разобраться, так как в офисе стало очень тесно! Вам нужно составить новую рассадку инженеров в офисе. Столы пронумерованы, и вы провели опрос среди инженеров, выяснив, за каким столом они работают сейчас, и за каким столом они хотели бы работать (может совпадать с тем столом, за которым они сейчас работают). Каждый инженер должен либо остаться на своем месте, либо переместиться на то место, которое он обозначил как желаемое. Никакие два инженера не работают сейчас за одним столом, и после пересадки никакие два инженера также не должны работать за одним столом.

Сколько существует способов рассадить инженеров так, чтобы удовлетворить описанным ограничениям? Ответ может быть большим, поэтому выведите его по модулю 1000000007 = 109 + 7.

Входные данные

В первой строке находится одно целое число N (1 ≤ N ≤ 100000) — количество инженеров.

Далее следуют N строк, в каждой из них находятся ровно два целых числа. Строка i содержит номер стола, за которым сейчас работает i-й инженер, и затем номер стола, за который i-й инженер хотел бы переехать. Столы пронумерованы от 1 до 2·N. Гарантируется, что никакие два инженера не работают сейчас за одним столом.

Выходные данные

Выведите число способов рассадить всех инженеров по модулю 1000000007 = 109 + 7.

Примеры
Входные данные
4
1 5
5 2
3 7
7 3
Выходные данные
6
Входные данные
5
1 10
2 10
3 10
4 10
5 5
Выходные данные
5
Примечание

Следующие рассадки возможны в первом примере:

  • 1 5 3 7
  • 1 2 3 7
  • 5 2 3 7
  • 1 5 7 3
  • 1 2 7 3
  • 5 2 7 3