Na poljani se nalazi n zečeva i n zečica. Svi oni stoje duž jedne linije tako da svizečevi gledaju desno niz liniju, a sve zečice levo niz liniju. Oni bi želeli da se podele uparove tako da u svakom paru bude jedna zečica i jedan zec koji mogu međusobno da se vide.Zec vidi zečicu ako je ona bilo gde desno od njega, a zečica vidi zeca ako je on bilo gdelevo od nje. Od vas se traži da izbrojte na koliko načina oni to mogu uraditi tako da sesvaki zec odnosno zečica nađe u tačno jednom paru. Pošto taj broj može biti veoma velik,nađite samo koliki ostatak daje taj broj pri deljenju sa 10007.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu zapisan je broj n.U drugom redu zapisano je tačno 2n simbola (bez razmaka) od kojih ima n znakova > kojioznačavaju zečeve (gledaju desno) i n znakova < koji označavaju zečice (gledaju levo).

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom redu ispisati samo jedanbroj - ostatak pri deljenju sa 10007 broja mogućih načina da se zečevi podele u parove.

Ograničenja:

• 1 ≤ n ≤ 100000
• vremensko ograničenje za izvršavanje programa je 1 s.

Primer 1:

3
>><><<

4

Objašnjenje:

Ako zečeve i zečice označimo brojem koji odgovara poziciji na kojoj se nalaze,četiri moguća načina formiranja parova su:

{(1, 6), (2, 3), (4, 5)},
{(1, 3), (2, 5), (4, 6)},
{(1, 3), (2, 6), (4, 5)} i
{(1, 5), (2, 3), (4, 6)}

Primer 2:

8
>>>>>>>><<<<<<<<

292

Objašnjenje:

Ukupan broj načina je 40320, što pri deljenju sa 10007 daje ostatak 292