Submission #227874

---

Source Code Expand

main :: IO ()
main = getContents >>= print . (`mod` 1000000007) . solve . map (map read . words) . lines

solve :: [[Integer]] -> Integer
solve ((r:c:_):(x:y:_):(d:l:_):_) = solve' (x, y) (d, l) * (r - x + 1) * (c - y + 1)
solve _ = 0

solve' :: Integral a => (a, a) -> (a, a) -> a
solve' (x, y) (d, l)
  | x * y == d + l = choose (x, y) (d, l)
  | otherwise = choose (x, y) (d, l)
              - choose (x - 1, y) (d, l) * 2
              - choose (x, y - 1) (d, l) * 2
              + choose (x - 2, y) (d, l)
              + choose (x, y - 2) (d, l)
              + choose (x - 1, y - 1) (d, l) * 4
              - choose (x - 2, y - 1) (d, l) * 2
              - choose (x - 1, y - 2) (d, l) * 2
              + choose (x - 2, y - 2) (d, l)

choose :: Integral a => (a, a) -> (a, a) -> a
choose (x, y) (d, l)
  | x * y < d + l = 0
  | otherwise = binomial (x * y) d * binomial (x * y - d) l

binomial :: Integral a => a -> a -> a
binomial n k | k <= 0 || n <= k || n <= 0 = 1
             | otherwise = product [k+1..n] `div` product [1..n-k]

Submission Info

Judge Result