一位严厉的计算机科学老师决定为学校网站上的昵称制定特殊的生成规则。他设定了一组形如“A B”的规则，这意味着字符 A 之后可以紧跟字符 B。一个昵称可以是任意长度恰好为 $K$ 的合法字符序列（即一个序列，其中每个字符（除第一个外）都可以根据规则紧跟在前一个字符之后，而第一个字符可以是给定字母表中的任意字符）。请计算根据给定规则可以生成的唯一昵称的总数。
输入格式
第一行包含三个整数 $N$、$M$ 和 $K$，其中 $N$ 是字母表中的字符数，$1 \le N \le 5000$，$M$ 是规则数，$0 \le M \le 5000$，$K$ 是给定的昵称长度，$1 \le K \le 5000$。接下来的 $M$ 行中，每行包含两个由空格分隔的自然数，表示字母表中的字符编号（从 $1$ 开始）。
输出格式
输出一个非负整数——长度为 $K$ 的合法昵称数量，对 $10^9 + 7$ 取模。
样例
样例输入 1
2 3 4 1 1 1 2 2 2
样例输出 1
5