Petar je nakon napornog radnog dana odlučio zaigrati igru svoga djetinjstva, Minesweeper. Nakon nekoliko odigranih partija (naravno, pobijeđenih) Petar vam je odlučio zadati jedan kombinatorički zadatak.

Pred vama je dvodimenzionalno polje veličine \(2 \times n\). U prvome retku nalaze se polja označena simbolima: \(0\), \(1\), \(2\), \(3\) ili \(?\). Brojevi označavaju koliko mina graniči tom polju s donje strane (neposredno dolje ili dijagonalno dolje u oba smjera), a \(?\) označava da tom polju s donje strane može graničiti bilo koji broj mina. Vaš je zadatak prebrojati na koliko načina se mogu postaviti mine u drugi redak tako da su zadovoljeni uvjeti svih polja u provme retku. Budući da taj broj može biti jako velik, ispišite ga modulo \(10^9+7\).

Napomena: Prazan red se također broji kao kombinacija (ukoliko to zadovoljava uvjete prvog reda).

Ulazni podatci

U prvome retku nalazi se prirodan broj \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)), duljina polja

U drugome retku nalazi se string duljine \(n\) koji se sastoji isključivo od znakova: \(0\), \(1\), \(2\), \(3\), \(?\)

Izlazni podatci

U prvi i jedini redak ispišite traženi broj kombinacija iz teksta zadatka, modulo \(10^9+7\).

Podzadatci

Ulaz primjera 1

4
??11

Izlaz primjera 1

4

Pojašnjenje primjera 1

Valjane kombinacije su:

??11  ??11  ??11  ??11
X..X  X.X.  ..X.  ...X

Ulaz primjera 2

4
????

Izlaz primjera 2

16

Ulaz primjera 3

6
11??3?

Izlaz primjera 3

2