A malicious computer science teacher has decided to introduce special rules for creating nicknames on the school website. He has set a collection of rules of the form "A B", which means that the character B can follow the character A. A nickname can be any valid sequence of characters of length exactly K. A nickname can be any sequence of characters where each character, except for the first one, can follow the previous one according to the rules, and the first character can be any character from the given alphabet. Determine the total number of unique nicknames that can be formed according to the given rules.

Input

The first line contains three integers $N$, $M$, and $K$, where $N$ is the number of characters in the alphabet, $1 \le N \le 5000$, $M$ is the number of rules, $0 \le M \le 5000$, and $K$ is the specified length of the nickname, $1 \le K \le 5000$. The following $M$ lines each contain two space-separated natural numbers representing the indices (starting from 1) of the alphabet characters.

Output

A single non-negative integer — the number of valid nicknames of length $K$, taken modulo $10^9 + 7$.

Examples

Input 1

2 3 4
1 1
1 2
2 2

Output 1

5