import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.IntMap as IM
main=print.solve.unfoldr(B.readInt.B.dropWhile isSpace)=<<B.getContents
solve(n:as)=fst$foldl f(1,IM.empty)as
f(k,m)a=(k*(g 3(a-1)m-g 0 a m)`mod`(10^9+7),IM.insertWith(+)a 1 m)
g=IM.findWithDefault