Hrvatska lutrija nedavno je predstavila novu igru nazvanu "Veće ili Manje".
U ovoj igri, igrači su pozvani da odaberu hoće li broj na trenutnoj loptici biti veći ili manji od broja na prethodnoj loptici, počevši od druge loptice pa nadalje. Loptice su numerirane od 1 do n i izvlače se iz bubnja nasumičnim redoslijedom. Prije svakog izvlačenja, igrači popunjavaju listiće s \(n - 1\) polja, gdje mogu označiti "Veće" ili "Manje". Hrvoje, dugogodišnji ovisnik o igrama na sreću, upravo je ispunio svoj listić i sada želi saznati vjerojatnost svoje pobjede.

Ulazni podatci:

U prvom redu se nalazi priodan broj n (2 <= n <= 5000) broj loptica.
U drugom redu se nalazi binarni niz duljine n - 1 gdje a[i] = 0 predstavlja zaokruženo "Manje" na listiću a a[i] = 1 zaokruženo "Veće" za lopticu i + 1.

Izlazni podatci:

Ako je šansa da Hrvoje pobjedi skračeni razlomak a/b ispišite jedan cijeli broj c <= 10^9 + 7 takav da (c * b) % (10^9 + 7) = a % (10^9 + 7)

Podzadatci

Ulaz primjera 1

2
1

Izlaz primjera 1

500000004

Ulaz primjera 2

5
1010

Izlaz primjera 2

933333340

Objašnenje primjera 1

Šansa da je druga loptica veća od prve je 50% ili 1/2.
2 * 500000004 = 1000000008 % (10^9 + 7) = 1