Description
Given a directed graph with N vertices, M edges. For all vertex pairs (u, v), find the number of different paths (a path can walk through a same edge more than once) starting from u and ending at v that contains exactly K edges (mod 1919810513).
Input
The first line contains three integers N, M, and K, which are the number of vertices, number of edges, and how many edges should a path contain respectively.
The second to (M + 1)th line, each line consists of two integers ui and vi, representing an edge starting from vertex ui and ending at vertex vi.
Output
Note that there is no space before newline.