Give a positive interger n and matrix \(A=(a_{ij})_{m*m}\). The task is to cal Aⁿ%(10⁹+7).

Input: 

- The firsst line contains 2 positive interger n (n<=10¹⁸) and m(m<=10).

- m lines folows contains matrix \(A=(a_{ij})_{m*m}, |a_{ij}|\leq10\)

Output:  m line print matrix Aⁿ%(10⁹+7).