Розглянемо орієнтований граф, який має \(n\) вузлів і \(m\) ребер. Ваше завдання полягає в тому, щоб підрахувати кількість шляхів від вузла 1 до вузла \(n\) з рівно \(k\) ребер.

Вхідні дані

Перший рядок містить три цілі числа \(n, m, k\): кількість вузлів і ребер, а також довжину шляху. Вузли пронумеровані 1,2,…,\(n\).

Далі ідуть \(m\) рядків, що описують ребра. Кожен рядок містить два цілі числа \(a\) і \(b\): це ребро від вузла \(a\) до вузла \(b\).

Вихідні дані

Вивести кількість шляхів за модулем \(10^9+7\).

Обмеження

• \(1≤n≤100\)
• \(1≤m≤n( n−1)\)
• \(1≤k≤10^9\)
• \(1≤a,b≤n\)

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

3 4 8
1 2
2 3
3 1
3 2

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

2