{-# LANGUAGE BangPatterns      #-} --引数に!

import Data.List
import Data.Bits
import Data.Maybe (fromJust)
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Matrix.Unboxed
import Control.Monad
--import Debug.Trace

(.**.) :: Num a => Matrix a -> Matrix a -> Matrix a
(.**.) = multStd2

solve :: Int -> Int -> Matrix Int -> Int
solve n k mat = sub 0 (identity n) mat
  where
    mod'' = mapPos (\_ a -> mod' a)
    sub i mat mat2 | bit i > k   = foldl1' (\a b -> mod' (a+b)) $ toList mat
                   | testBit k i = sub (i+1) (mod'' $ mat .**. mat2) (mod'' $ mat2 .**. mat2)
                   | otherwise   = sub (i+1) mat (mod'' $ mat2 .**. mat2)

main :: IO ()
main = print . mainIn =<< B.getContents
---------------------------------------------

mainIn :: B.ByteString -> Int
mainIn cont =
   let remLines0 = map (map readBInt. B.words) $ B.lines cont
       [n,k]:remLines1 = remLines0
       mat = fromLists remLines1
   in solve n k mat

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

mod' :: Int -> Int
mod' n = if n < 1000000007 then n else mod n 1000000007
