Submission #4704278

---

Source Code Expand

import Data.Int
import Data.List

modulo :: Int64
modulo = 10^9 + 7
newtype N = N Int64 deriving Eq
instance Show N where
  show (N x) = show x
instance Num N where
  N x + N y = N ((x + y) `rem` modulo)
  N x - N y = N ((x - y) `mod` modulo)
  N x * N y = N ((x * y) `rem` modulo)
  fromInteger n = N (fromInteger (n `mod` fromIntegral modulo))
  abs = undefined; signum = undefined

solution :: [(N,N,N)]
solution = (1,0,0):(4,0,1):(16,1,4):(61,3,15)
  : zipWith4 (\(a1,b1,c1) (a2,b2,c2) (a3,b3,c3) (a4,b4,c4) -> (4*a1-3*a3+b3+c3-3*a4,a2-c2,a1-b1)) (drop 3 solution) (drop 2 solution) (tail solution) solution

main = do
  n <- readLn :: IO Int
  print $ case solution !! n of
            (N x,_,_) -> x

Submission Info

Judge Result