Count Walks of Length K

A directed graph with n nodes is given by its adjacency matrix. Print the total number of walks of exactly k edges (over all start and end nodes) modulo 1,000,000,007.

1 <= n <= 50 1 <= k <= 10^9