module Main where genarrs :: Int -> [(Int, Int)] -- Generate all possible inner 1d intervals genarrs s = genarr 0 s where genarr _ 0 = [] genarr a b | a<=b = [(a,b)] ++ (genarr (a+1) b) | a>b = genarr 0 (b-1) cntoness :: (Int,Int) -> [Int] -> Int -- Count ones in 1d interval inside 1d array cntoness (a,b) xs | a > b = 0 | a > (length xs) || b > (length xs) = 0 | a <= b = (xs!!a) + cntoness ((a+1),b) xs -- Input array consists only of ones and zeros -- so we can use sum for count. cntonesa :: ((Int,Int), (Int,Int)) -> [[Int]] -> Int -- Count ones in 2d interval inside 2d array cntonesa (ab, (a,b)) xs | a > b = 0 | a > (length xs) || b > (length xs) = 0 | a <= b = (cntoness ab (xs!!a)) + cntonesa (ab, ((a+1),b)) xs genarrs2d :: Int -> Int -> [((Int, Int), (Int, Int))] -- Generate all possible inner 2d intervals genarrs2d a b = [(x, y) | x <- genarrs a, y <- genarrs b] readMatr :: Int -> Int -> IO [[Int]] readMatr w h = sequence . replicate h $ fmap (map read . take w . words) getLine main :: IO () main = do sizesln <- getLine let nums = map read $ words sizesln let w = nums!!0 let h = nums!!1 let n = nums!!2 let arr = readMatr w h let cnts = map (\x -> fmap (cntonesa x) arr) (genarrs2d (w-1) (h-1)) -- Coounts of ones in each array let fones = fmap (\x -> filter (==n) x) $ sequence cnts -- Array with only counts equals n fmap length fones >>= print