import Data.List
import Control.Monad

main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  xs <- replicateM n (map read . words <$> getLine) :: IO [[Int]]
  let ps = paths n xs
  print $ trav m 1 ps []

paths :: Int -> [[Int]] -> [(Int,[Int])]
paths 0 xs = []
paths n xs = 
  let 
    f = filter (\[a,_] -> a==n) xs
  in
    if null f then (paths (n-1) xs) else (n, last $ transpose f) : (paths (n-1) xs)

trav :: Int -> Int -> [(Int,[Int])] ->  [Int] -> Int
trav m current paths arrived
  | current `elem` arrived = 0
  | length arrived == m-1 = 1 
  | otherwise = 
    let 
      ds = filter (\(a,_) -> a==current) paths
    in
      if null ds 
         then if length arrived == m-1 then 1 else 0
         else sum $ [r | d<-(snd $ head ds), let r = trav m d paths (current:arrived)]