Розглянемо орієнтований граф, який має ~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