Uolevi päätti kirjoittaa n merkkiä sisältävän merkkijonon, jossa jokainen merkki on ( tai ). Lisäksi Uolevi haluaa, että merkkijono on oikein sulutettu, eli se voisi olla matemaattinen lauseke, josta on poistettu kaikki merkit paitsi sulut.

Uolevi kuitenkin väsyi kesken kirjoittamiseen, ja Maija joutuu kirjoittamaan merkkijonon loppuun. Montako tapaa hänellä on kirjoittaa merkkijono loppuun niin, että siitä tulee halutunlainen?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: merkkijonon haluttu pituus.

Toisella rivillä on merkeistä ( ja ) muodostuva merkkijono: merkkijonon alkuosa, jonka Uolevi kirjoitti. Siinä on ainakin yksi merkki ja enintään n merkkiä.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: mahdollisten merkkijonojen määrä. Vastaus voi olla suuri, joten tulosta se modulo 10^9+7.

Rajat

• 1 \le n \le 10^5

Esimerkki

Syöte:

6
(()

Tuloste:

2

Selitys: Mahdolliset merkkijonot ovat (())() ja (()()).