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