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

• $1 \le n \le 100$
• Säännöllisessä lausekkeessa on enintään $100$ merkkiä.

Esimerkki

Syöte:

10
0*10*10*

Tuloste:

45