Problem Statement

Consider a directed graph that has n nodes and m edges. Your task is to count the number of paths from node 1 to node n with exactly k edges. Input Format: The first input line contains three integers n, m and k: the number of nodes and edges, and the length of the path. The nodes are numbered 1, 2, ..., n. Then, there are m lines describing the edges. Each line contains two integers a and b: there is an edge from node a to node b. Output Format: Print the number of paths modulo 10 9 + 7. Constraints 1 ≤ n ≤ 100 1 ≤ m ≤ n(n - 1) 1 ≤ k ≤ 10 9 1 ≤ a, b ≤ n Examples: Example 1: Input: 5 3 17 5 2 5 5 3 3 Output: 0