{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE BinaryLiterals             #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DeriveFunctor              #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE DerivingVia                #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE KindSignatures             #-}
{-# LANGUAGE LambdaCase                 #-}
{-# LANGUAGE MagicHash                  #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE MultiWayIf                 #-}
{-# LANGUAGE NumericUnderscores         #-}
{-# LANGUAGE OverloadedStrings          #-}
{-# LANGUAGE PatternSynonyms            #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE RecordWildCards            #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TupleSections              #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeInType                 #-}
{-# LANGUAGE UnboxedTuples              #-}
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
{- base -}
import           Control.Applicative
import qualified Control.Arrow                     as Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import qualified Data.Char                         as Char
import           Data.Complex
import qualified Data.Foldable                     as Foldable
import           Data.Function
import qualified Data.List                         as List
import           Data.Maybe
import           Data.Monoid
import           Data.Ord
import           Data.Ratio
import           Data.Semigroup
import qualified Data.Word                         as Word
import           Foreign                           hiding (void)
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array.IO                     as ArrIO
import qualified Data.Array.MArray                 as ArrMA
import qualified Data.Array.ST                     as ArrST
import qualified Data.Array.Storable               as ArrStore
import qualified Data.Array.Unboxed                as ArrU
{- bytestring -}
import qualified Data.ByteString                   as BS
import qualified Data.ByteString.Builder           as BSB
import qualified Data.ByteString.Builder.Extra     as BSBE
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.ByteString.Lazy              as BSL
import qualified Data.ByteString.Lazy.Builder      as BSLB
import qualified Data.ByteString.Lazy.Char8        as BSLC8
import qualified Data.ByteString.Unsafe            as BSU
{- containers -}
import qualified Data.Graph                        as Graph
import           Data.IntMap                       (IntMap)
import qualified Data.IntMap                       as IntMap
import           Data.IntSet                       (IntSet)
import qualified Data.IntSet                       as IntSet
import qualified Data.Sequence                     as Seq
import qualified Data.Tree                         as Tree
{- integer-gmp -}
import           GHC.Integer.GMP.Internals
{- time -}
import qualified Data.Time.Calendar                as Calender
import qualified Data.Time.Calendar.Easter         as CalenderE
import qualified Data.Time.Calendar.Julian         as CalenderJ
import qualified Data.Time.Calendar.MonthDay       as CalenderM
import qualified Data.Time.Calendar.OrdinalDate    as CalenderD
import qualified Data.Time.Calendar.WeekDate       as CalenderW
import qualified Data.Time.LocalTime               as LocalTime
{- transformers -}
import qualified Control.Monad.Trans.Accum         as TAccum
import qualified Control.Monad.Trans.Cont          as TCont
import qualified Control.Monad.Trans.Identity      as TId
import qualified Control.Monad.Trans.Reader        as TReader
import qualified Control.Monad.Trans.State.Lazy    as TStateL
import qualified Control.Monad.Trans.State.Strict  as TStateS
import qualified Control.Monad.Trans.Writer.CPS    as TWriteC
import qualified Control.Monad.Trans.Writer.Lazy   as TWriteL
import qualified Control.Monad.Trans.Writer.Strict as TWriteS
{- vector -}
import qualified Data.Vector                       as V
import qualified Data.Vector.Generic               as VG
import qualified Data.Vector.Generic.Mutable       as VGM
import qualified Data.Vector.Mutable               as VM
import qualified Data.Vector.Primitive             as VP
import qualified Data.Vector.Primitive.Mutable     as VPM
import qualified Data.Vector.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
main :: IO ()
main = do
  (a, b) <- parse2
  print $ a *% b
-------------------------------------------------------------------------------
#define MOD 1000000007

modulus :: (Num a) => a
modulus = MOD
{-# INLINE modulus #-}

infixr 8 ^%
infixl 7 *%, /%
infixl 6 +%, -%

(+%) :: Int -> Int -> Int
(+%) (I# x#) (I# y#) = case x# +# y# of
  r# -> I# (r# -# ((r# >=# MOD#) *# MOD#))
{-# INLINE (+%) #-}

(-%) :: Int -> Int -> Int
(-%) (I# x#) (I# y#) = case x# -# y# of
  r# -> I# (r# +# ((r# <# 0#) *# MOD#))
{-# INLINE (-%) #-}

(*%) :: Int -> Int -> Int
(*%) (I# x#) (I# y#) = I# ((x# *# y#) `remInt#` MOD#)
{-# INLINE (*%) #-}

(/%) :: Int -> Int -> Int
(I# x#) /% (I# y#) = go# y# MOD# 1# 0# where
  go# a# b# u# v#
    | isTrue# (b# ># 0#) = case a# `quotInt#` b# of
                                q# -> go# b# (a# -# (q# *# b#)) v# (u# -# (q# *# v#))
    | otherwise = I# ((x# *# (u# +# MOD#)) `remInt#` MOD#)
{-# INLINE (/%) #-}

(^%) :: Int -> Int -> Int
(^%) x n
  | n > 0     = go 1 x n
  | n== 0     = 1
  | otherwise = go 1 ((/%) 1 x) (-n)
  where
    go !acc !y !m
      | m .&. 1 == 0 = go acc (y *% y) (unsafeShiftR m 1)
      | m == 1       = acc *% y
      | otherwise    = go (acc *% y) (y *% y) (unsafeShiftR (m - 1) 1)
{-# INLINE (^%) #-}

intMod :: (Integral int) => int -> Mint
intMod x = fromIntegral $ mod (fromIntegral x) MOD
{-# INLINE intMod #-}

intModValidate :: Mint -> Bool
intModValidate (Mint x) = 0 <= x && x < MOD
{-# INLINE intModValidate #-}


newtype Mint = Mint { getMint :: Int }
  deriving newtype (Eq, Ord, Read)

instance Show Mint where
  show (Mint x) = show x
instance Num Mint where
  (+) = coerce (+%)
  (-) = coerce (-%)
  (*) = coerce (*%)
  abs = id
  signum = const (Mint 1)
  fromInteger x = coerce @Int @Mint . fromInteger $ mod x MOD
instance Real Mint where
  toRational (Mint x) = toRational x
instance Bounded Mint where
  minBound = Mint 0
  maxBound = Mint $ MOD - 1
instance Enum Mint where
  toEnum = intMod
  fromEnum = coerce
instance Fractional Mint where
  (Mint x) / (Mint y) = Mint (x /% y)
  fromRational q      = fromInteger (numerator q) / fromInteger (denominator q)
instance Integral Mint where
  quotRem x y = (x / y, x - x / y * y)
  toInteger = coerce (toInteger @Int)

newtype instance VUM.MVector s Mint = MV_Mint (VUM.MVector s Int)
newtype instance VU.Vector Mint     =  V_Mint (VU.Vector Int)

instance VU.Unbox Mint
instance VGM.MVector VUM.MVector Mint where
  {-# INLINE basicLength #-}
  basicLength (MV_Mint v) = VGM.basicLength v
  {-# INLINE basicUnsafeSlice #-}
  basicUnsafeSlice i n (MV_Mint v) = MV_Mint $ VGM.basicUnsafeSlice i n v
  {-# INLINE basicOverlaps #-}
  basicOverlaps (MV_Mint v1) (MV_Mint v2) = VGM.basicOverlaps v1 v2
  {-# INLINE basicUnsafeNew #-}
  basicUnsafeNew n = MV_Mint `fmap` VGM.basicUnsafeNew n
  {-# INLINE basicInitialize #-}
  basicInitialize (MV_Mint v) = VGM.basicInitialize v
  {-# INLINE basicUnsafeReplicate #-}
  basicUnsafeReplicate n x = MV_Mint `fmap` VGM.basicUnsafeReplicate n (coerce x)
  {-# INLINE basicUnsafeRead #-}
  basicUnsafeRead (MV_Mint v) i = coerce `fmap` VGM.basicUnsafeRead v i
  {-# INLINE basicUnsafeWrite #-}
  basicUnsafeWrite (MV_Mint v) i x = VGM.basicUnsafeWrite v i (coerce x)
  {-# INLINE basicClear #-}
  basicClear (MV_Mint v) = VGM.basicClear v
  {-# INLINE basicSet #-}
  basicSet (MV_Mint v) x = VGM.basicSet v (coerce x)
  {-# INLINE basicUnsafeCopy #-}
  basicUnsafeCopy (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeCopy v1 v2
  {-# INLINE basicUnsafeMove #-}
  basicUnsafeMove (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeMove v1 v2
  {-# INLINE basicUnsafeGrow #-}
  basicUnsafeGrow (MV_Mint v) n = MV_Mint `fmap` VGM.basicUnsafeGrow v n

instance VG.Vector VU.Vector Mint where
  {-# INLINE basicUnsafeFreeze #-}
  basicUnsafeFreeze (MV_Mint v) = V_Mint `fmap` VG.basicUnsafeFreeze v
  {-# INLINE basicUnsafeThaw #-}
  basicUnsafeThaw (V_Mint v) = MV_Mint `fmap` VG.basicUnsafeThaw v
  {-# INLINE basicLength #-}
  basicLength (V_Mint v) = VG.basicLength v
  {-# INLINE basicUnsafeSlice #-}
  basicUnsafeSlice i n (V_Mint v) = V_Mint $ VG.basicUnsafeSlice i n v
  {-# INLINE basicUnsafeIndexM #-}
  basicUnsafeIndexM (V_Mint v) i = coerce `fmap` VG.basicUnsafeIndexM v i
  basicUnsafeCopy (MV_Mint mv) (V_Mint v) = VG.basicUnsafeCopy mv v
  {-# INLINE elemseq #-}
  elemseq _ = seq

fact :: Int -> Mint
fact = VU.unsafeIndex factCache
{-# INLINE fact #-}

recipFact :: Int -> Mint
recipFact = VU.unsafeIndex recipFactCache
{-# INLINE recipFact #-}

invFact :: Int -> Mint
invFact x = recipFact x * fact (x - 1)
{-# INLINE invFact #-}

nPk :: Int -> Int -> Mint
nPk n k
  | n < k     = 0
  | otherwise = fact n * recipFact k
{-# INLINE nPk #-}

nCk :: Int -> Int -> Mint
nCk n k
  | n < k     = Mint 0
  | otherwise = fact n * recipFact (n - k) * recipFact k
{-# INLINE nCk #-}

nHk :: Int -> Int -> Mint
nHk n k
  | n < 0 || k < 0 = Mint 0
  | k == 0         = Mint 1
  | otherwise      = nCk (n + k - 1) k
{-# INLINE nHk #-}

#define FACT_CACHE_SIZE 200000

factCacheSize :: Int
factCacheSize = min (modulus - 1) FACT_CACHE_SIZE
{-# INLINE factCacheSize #-}

factCache :: VU.Vector Mint
factCache = VU.scanl' (\ x y -> x * coerce y) (1 :: Mint) $ VU.generate factCacheSize (+ 1)
{-# NOINLINE factCache #-}
recipFactCache :: VU.Vector Mint
recipFactCache = VU.scanr' ((*) . coerce) (1 / factCache VU.! factCacheSize) $ VU.generate factCacheSize (+ 1)
{-# NOINLINE recipFactCache #-}
-------------------------------------------------------------------------------
fi :: Int -> Integer
fi = fromIntegral
fI :: Integer -> Int
fI = fromInteger

gcdInt :: Int -> Int -> Int
gcdInt a b = fI $ gcdInteger (fi a) (fi b)

gcdextInt :: Int -> Int -> (Int, Int)
gcdextInt a b = case gcdExtInteger c d of
  (# x, y #) -> (fI x, fI y)
  where
    c = fromIntegral a
    d = fromIntegral b

lcmInt :: Int -> Int -> Int
lcmInt a b = fI $ lcmInteger (fi a) (fi b)

sqrInt :: Int -> Int
sqrInt = fI . sqrInteger . fi

powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo)

recipModInt :: Int -> Int -> Int
recipModInt x n = fI $ recipModInteger (fi x) (fi n)
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine
  return $ VU.unzip vectup
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine
  return $ VU.unzip3 vectup
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------