Code Submission Evaluation System Login

BOI-leiri 2019

Merkkijonot


Task | Statistics


CSES - MerkkijonotCSES - Merkkijonot

Time limit:1.00 s Memory limit:512 MB

Tehtäväsi on laskea, moniko $n$ merkin pituinen bittijono täsmää annettuun säännölliseen lausekkeeseen.

Syöte

Syötteen ensimmäisellä rivillä on luku $n$: merkkijonon pituus.

Syötteen toisella rivillä on säännöllinen lauseke, jossa voi olla merkkejä 0 ja 1, vaihtoehtoja |, toistoja * sekä sulkuja.

Tuloste

Tulosta yksi kokonaisluku: merkkijonojen määrä modulo $10^9+7$.

Rajat
Esimerkki

Syöte:
10
0*10*10*


Tuloste:
45