시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB51150.000%

문제

Jūratė žaidžia kortų žaidimą. Iš pradžių ji rankose turi N kortų; kiekvieną kortą nusako jos rūšis ir skaičius. Visos kortos skirtingos.

Jūratė deda kortas į krūvelę. Iš pradžių ji padeda vieną pasirinktą kortą. Po to ji kiekvienu ėjimu ant prieš tai padėtos kortos deda vieną iš turimų kortų, kuri:

  • arba turi tokį patį skaičių, kaip prieš tai padėta korta,
  • arba yra tos pačios rūšies, bei turi didesnį skaičių.

Pavyzdžiui, jei krūvelės viršuje esanti korta yra ♦4, ji ant viršaus galėtų dėti ♦5, ♦8 arba ♣4, bet negalėtų dėti ♦3 arba ♣5.

Po to, kai Jūratė padeda pirmąją kortą, ji bet kada gali baigti žaidimą.

Kadangi Jūratė mėgsta žaisti ilgai, jai įprastos kortų kaladės nepakanka. Todėl vienos rūšies kortų gali būti daugiau nei įprastai, o rūšių gali būti daugiau nei keturios. Kiekvieną rūšį apibūdina jos numeris.

Reikia rasti, kiek yra skirtingų kortų krūvelių, kurios gali susidaryti žaidimo pabaigoje. Dvi krūvelės laikomos skirtingomis, jei nesutampa jose esančios kortos arba jų tvarka. Atsakymą pateikite moduliu 1 000 000 007.

입력

Pirmojoje eilutėje pateiktas sveikasis skaičius N – pradiniu momentu Jūratės rankose laikomų kortų skaičius

Tolimesnėse N eilučių pateikta po du tarpu atskirtus sveikuosius skaičius ai ir bi – i-tos kortos rūšis bei ant jos parašytas skaičius.

출력

Išveskite vienintelį skaičių – skirtingų įmanomų krūvelių, likusių po žaidimo, skaičių moduliu 1 000 000 007.

제한

  • 3 ≤ N ≤ 1 000 000
  • 1 ≤ ai, bi ≤ N

서브태스크

번호배점제한
113

ai ≤ 4, bi ≤ 13 (įprastinė kaladė)

218

ai ≤ 2

320

bi ≤ 2

432

N ≤ 1 000

517

Papildomų ribojimų nėra

예제 입력 1

4
1 1
1 2
2 2
2 3

예제 출력 1

11

Žemiau pateiktos visos galimos krūvelės – po vieną krūvelę eilutėje. Kortos pateiktos nuo krūvelės apačios formatu (rūšis, skaičius).

  • (1, 1)
  • (1, 1) (1, 2)
  • (1, 1) (1, 2) (2, 2)
  • (1, 1) (1, 2) (2, 2) (2, 3)
  • (1, 2)
  • (1, 2) (2, 2)
  • (1, 2) (2, 2) (2, 3)
  • (2, 2)
  • (2, 2) (1, 2)
  • (2, 2) (2, 3)
  • (2, 3)

채점 및 기타 정보

  • 예제는 채점하지 않는다.