Graph Paths I

Problem Statement

Graph Paths I Problem Consider a directed graph with n nodes and m edges. The nodes are numbered 1, 2, ..., n . Count the walks that start at node 1 , end at node n , and use exactly k edges. A walk may visit the same node any number of times and may reuse the same edge any number of times; only the number of edges it uses is fixed. Report the count modulo 1000000007 . Input Format Line 1: three integers n , m and k -- the number of nodes, the number of edges, and the required number of edges in the walk. Next m lines: two integers a and b , meaning there is a directed edge from node a to node b . An ordered pair may be listed more than once, and each listing is a separate edge. Self loops, that is edges with a equal to b , are allowed. Output Format Print one integer: the number of walks from node 1 to node n using exactly k edges, modulo 1000000007 . Constraints 1 <= n <= 80 1 <= m <= 6400 1 <= k <= 10^9 1 <= a <= n and 1 <= b <= n The values n , m and k