m@main=getLine>>=putStrLn.(>>=(>>=p.read)).scanl1(zipWith(++)).scanr((:).(:[]))[]>>m
p x=show$product[2..x-2]^2`mod`max 1x