Na poljani se nalazi n zečeva i n zečica. Svi oni stoje duž jedne linije tako da svi zečevi gledaju desno niz liniju, a sve zečice levo niz liniju. Oni bi želeli da se podele u parove 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 gde levo od nje. Od vas se traži da izbrojte na koliko načina oni to mogu uraditi tako da se svaki 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 nalaze u datoteci zecovi.in) U prvom redu zapisan je broj n. U drugom redu zapisano je tačno 2n simbola (bez razmaka) od kojih ima n znakova > koji označavaju zečeve (gledaju desno) i n znakova < koji označavaju zečice (gledaju levo).

Izlaz:

(Izlazne podatke upisati u datoteku zecovi.out) U prvom redu ispisati samo jedan broj - 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

const
  fin = 'zecovi.in';
  fout = 'zecovi.out';


var
  res : Longint;


  procedure ReadInputAndSolve();
  var
    f : Text;
    n, i, z : Longint;
    ch : Char;
  begin
    Assign(f, fin);
    Reset(f);

    Readln(f, n);

    res := 1;
    z := 0;
    for i := 1 to 2*n do
    begin
      Read(f, ch);
      if ch = '>' then
        Inc(z)
      else
      begin
        res := (res * z) mod 10007;
        Dec(z);
      end;
    end;

    Close(f);
  end;


  procedure WriteOutput();
  var
    f : Text;
  begin
    Assign(f, fout);
    Rewrite(f);
    Writeln(f, res);
    Close(f);
  end;


begin
  ReadInputAndSolve();
  WriteOutput;
end.