module Main where

removeNth :: Int -> [a] -> [a]
removeNth 1 (x:xs) = xs
removeNth n (x:xs) = x : removeNth (n - 1) xs
removeNth _ [] = []

-- permutations of a matrix with one or zero rows and one or zero colums removed.
gridPermutations :: [[a]] -> [[[a]]]
gridPermutations xs =  [map (removeNth i) . (removeNth j) $ xs 
						| i <- [1..length xs], j <- [i..(length (xs !! 0))]]
					++ [map (removeNth i) xs | i <- [1..length xs]]
					++ [removeNth j xs | j <- [1..length (xs !! 0)]]

count :: Eq a => a -> [a] -> Int
count _ [] = 0
count a (x:xs)
	| a == x = 1 + count a xs
	| otherwise = count a xs

countMatrixElems :: Eq a => a -> [[a]] -> Int
countMatrixElems a = sum . map (count a)

main :: IO ()
main = interact
	$ show
	. (\(k, grid) -> 
		length
		. filter (== (read k))
		. map (countMatrixElems '#')
		$ gridPermutations grid)
	. (\(x:xs) -> ((words x) !! 2, xs))
	. lines
