Фермер Джон наймає нового ватажка стада своїх корів. Для цього він проінтерв'юював ~N~ (~2≤N≤10^9~ ) корів. Кожному він призначив " рівень компетенції " - число трохи більше ~C~ (~1≤C≤10^4~ ).

Тому що він провів багато інтерв'ю, ФД забув усі ці рівні компетенції. Однак він запам'ятав ~Q~ (~1≤Q≤min(N-1,100) ~) пар чисел (~a_i,h_i~) де ~h_i~ - номер першої корови, з рівнем компетенції строго більшим ніж у корів від 1 до ~a_i~ (~1≤a_i<h_i≤N ~). </p>

ФД сказав Вам ~Q~ пар (~a_i, h_i~). Допоможіть йому порахувати скільки послідовностей рівнів компетенції відповідають цій інформації. Оскільки число дуже велике, виводьте його за модулем ~10^9+7~

Формат вхідних даних

Перший рядок містить ~N, Q, C~.

Кожен з наступних рядків ~Q~ містить пару (~a_i,h_i~). Гарантується, що всі ~a_i~ різні.

Формат вихідних даних

Вивести кількість за модулем ~10^9+7~ послідовностей компетенцій, відповідних інформації ФД.

Оцінювання

• Тести 3-4 (10 балів): ~N \leq 10~ і ~Q, C \leq 4~.
• Тести 5-7 (20 балів): ~N, C \leq 100~.
• Тести 8-10 (20 балів): ~N \leq 2000~ і ~C \leq 200~.
• Тести 11-15 (20 балів) ~N, C \leq 2000~.
• Тести 16-20 (30 балів) Немає додаткових обмежень

Приклад вхідних даних

6 2 3
2 3
4 5

Приклад вихідних даних

6

Тільки наступні шість послідовностей відповідають інформації ФД:

1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3

Приклад вхідних даних

10 1 20
1 3

Приклад вихідних даних

399988086