ABC009D.hs

import           Data.Word
import           Data.Bits
import           Data.Vector (Vector)
import qualified Data.Vector as V
import           Data.Matrix ((<->), Matrix, matrix, nrows, ncols, getRow, getCol)
import qualified Data.Matrix as M
import qualified Data.List as List
import           Control.Applicative ((<$>))

toWord32 :: Int -> Word32
toWord32 = fromIntegral

prod :: Matrix Word32 -> Matrix Word32 -> Matrix Word32
prod m m' = matrix (nrows m) (ncols m) $
            (\(i,j) -> V.foldl xor (toWord32 0) $ V.zipWith (.&.) (getRow i m) (getCol j m'))

power :: Int -> Matrix Word32 -> Matrix Word32 -> Matrix Word32
power 0 acc _ = acc
power n acc m = power (n-1) (acc `prod` m) m

power' :: [Word8] -> Matrix Word32 -> Matrix Word32 -> Matrix Word32
power' [] acc _     = acc
power' (n:ns) acc m = if n == 1
                        then power' ns (acc `prod` m) (m `prod` m)
                        else power' ns acc (m `prod` m)

toBits :: Int -> [Word8]
toBits 0         = fromIntegral 0 : []
toBits 1         = fromIntegral 1 : []
toBits n | n > 1 = (fromIntegral (n `mod` 2)) : (toBits $ n `div` 2)

solve :: Int -> Vector Word32 -> Vector Word32 -> Word32
solve n as cs | n >= 0 =  let size = V.length cs
                              m = joinMatrix size $ M.rowVector cs
                          in  M.getElem 1 1 $ (power' (toBits n) (identmat size) m) `prod` (M.colVector as)
  where
    joinMatrix :: Int -> Matrix Word32 -> Matrix Word32
    joinMatrix n cs = cs <-> (M.submatrix 1 (n-1) 1 n $ identmat n)
    identmat s = let n = s - 1
                 in M.fromLists $
                      [ (replicate i 0) ++ [complement 0] ++ replicate (n-i) 0
                      | i <- [0..n] ]

main :: IO ()
main = do
  [k, m] <- readInts
  a <- V.fromList . map toWord32 . List.reverse <$> readInts
  c <- V.fromList . map toWord32 <$> readInts
  let result = solve (m-k) a c
  putStrLn $ show result
    where
      readInt :: String -> Int
      readInt = read
      readInts :: IO [Int]
      readInts = map readInt . words <$> getLine