/*
`    -~          `                   ` ````` ...------...   `
`  `  `  `  `  `  `  `   `  `  `  `  `  `  `  `  `  `  `  `  `  `   `  `              `   ` .       `            `  `  ``` `` ``  _~<<<~~~~~~~~~~_-. ``                  `  `
`   `  `  `  `  `  `  `  `   `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `   ` ```   ` ~_`      ``  `  `  `  `  `  ` .(+&&&+-.. ``         `  _<~-                        `  ` ` `` ` ` ` ` ` `
`                 `    `                                     `  `  `  `  `  `    ``  ` -:_  ` `` `  `        ` `  `  (dMHHHHMHHmme-..  ` `  `  `  `_ `  `
` `    ` ` ` `  `  ` `   `   ` ` ` ` `  ` ` ` ` ` ` ` ` ` ` ` `  `      `       `  `   `` ` ~~_   ` ``     ` `  `  ` `  .uWHHHHHHHHHHHHMHmm+-.``  `  `` ~               `
` `  `   `  ` `  ` `  `          `  `   `   `   `   `   `  `   ` ` `  `  `      `   ````...``     `  ` `  `  `  `  .JXMHHHHHHHMMMMHHHHH@MHm+.  ``  ` _     `            `  `  `          `  `
`  ` `           `    `  `  `          `    `       `   `     `              `  `    `   `-(_ ` `  `          `  `  (dMHHHHHHHMM0C77TTUUWHMMHMH&.   ` .    `    `                  `             `
`     ` ` ` `    `  ` `  `  `` `    `  `  `  ` `  ` ` `  ``  ` `` `  ` ` ` ` `` ` `    ``.<<  ``` ` ``  ` `  ` ` .uH@HHMMMMMHMS>_````  `~?OWHMMHx.` -                                `
`   `   `  ``         `  `   `    `  `  `  ` `   `  `   `  `  ` `   ....-((+++++zzzzzxzzz+(((----...   ``  `.JdH@HHW0COXHMKI_.````   `  _?UM#Ny-_ ` `  `  `                 `        `         `
` ` `  `      `    `` ` (a+     `  ` `  `     `    `  `  ` `` `  ..-((++==lztrrrvvvzzzzzzzzuuzzrrtttll=1?<<<__-..jWqHW0z<;+dHH9>_``````` ` ` ` (WNMH>`` ` `       `       `  `               `   `
`  ` ` `    `   ` .(uHMR_  `  `  `    ` ``  ` `  `  ``  ..-_(<><<<<<<:::<1zrrrrrrrrrrrrrrrrtttll===?===?1+<;<+1OUUOz<+jdHH6! `` ` ` `...    (HMHHI.```   `  `                    `
`     `    `     `  .(WHHHH>   `  `  `  `  `  `   ``   .-(+<><<<:~_((((++zzOOOvz<<<<<<?++11<<<<~~~~<<<<<<<+1zllzzz+<(<<1OXUUC~ `     ` .dHNm&-.?WM#MR+__...`    `       `       `      `
-. `  `  `  ` `      (WHHHHMR_`  `  `  `       ` `  .-((;>;;<(((++zlz11zOOz<<<~~~~~~~~~~~~~~~~~.~~~.~~~~~~~~~~_~<<+zOOz++;<?<_- ````` .JdM#HHMHm-(vHM8I~_ `   `      `                     `  `  `   `
wXA&--.   `    ` `  .d@H@@@HH>   `  ` `  ` `` ` ..(++???+zzzllzz<<<<~~<<<~~~~.~~.~.~~.~~.~~.~~.~~~.~~.~~~~.~~.~~.~~~~~<?1zz+<::__. ` (dWHHHHHHHMNmkUC!`     ` ` `           `       `
_?7UWWkA+-.     `  `(d@@@@@@Mr    `  `  `  ` .-(+===zztltlOz<<~~~~~~_~~~~~~~~~~.~.~~.~~.~~.~~.~~.~~.~~.~.~~~.~~.~...~.~...__<<:~(<(-(zZ0WH@@HHHHHMD! `  `  `     `             `       `
`  ??UHHHk&-. `   ` jHH@@@@@R.         ` .((zOttrrtttOz<<<_.~~~~~~:~~~~~~~.~~~~~~.~~.~~.~~~.~~.~.~~.~~~~.~~~~~~~~~..~..~.......___<zOOdHH@@@@HMMHk<   ` `  ` `    `   `          `       `         `
`` ??UHHHkA+.     ?WH@@@@K_  ` `  ` .(zwwwzvrrrOOz<<_...~.~~~~~~~~~~~~~~.~.~.~~.~~.~~.~.~~.~~.~.~~.~~~.~~~~~.~~~~.~..~.........__<?UHMggHHH9UVUw<     `  `  `         `                  `  `
`   `` ??UHHWks-.   ?WH@@@Hl_____-.(+wuuuZuuuzZz<<~..~~~.~~~~~~~~~~~~~~~~~~~.~~.~~.~~.~~~.~.~.~~.~.~.~~~~.~~~~.~.~.~.~..........`.`._?7UWWk&++zzXw+  `  `   `  `  `       `         `
`   `  ``` ?7WHHkk&-  ?W@gH0>~_~~~~+wyyZyyZX0OI<<(:~~~~~.__~~~..~_--_~~~~.~~~~~.~.~~.~~~~.~.~~.~~~.~~~.~~~~~~___~..~.~.~.~........```..._~?TWHWkwXWk<     `          `  `     `   `              `
` `  `  ` ` _?4WHWWA-.(TH6~-..~~~:<zUyyZXVI???<<~.~..._(<<.._((zwZI<~~.~~..~..~.~.~..~.(_~.~~.~.~~~.~~....~.~_<_~~.~.~.~..........````.`. _~?zUWkkkI_ `      `  `                      `
`   `   `  `` ` _?TWffk+(<`-_:__:~_`_+XyXwz??<<<~.~.~._+z<_-(jw0Vz<_.....~...~~...~..~.._<_~.~~.~.~~.~~.~..~.~~~<<_.~.~.~.~~........``.`...` _<>?7TUI<. ```` `  ` `  `     `               `  `    `
`  `  ````    ` _?VWbI_  _::~~_``-(OVUVOz<<~~.~.~.(zZ>__(wVz<~_...........__.........~(<_~..~.~..~..~.~~.~.~~_<<_~.~~.~.~~........`.`..`.`` (><_~__~~___.  `    `   `       `   `
`  `   .-((+++zzzzz&++zwWk+. -_~:__``-+zz<><::~~.....(zOv_(jZI~.~...~...~..~~~(;_...~.~~.._?<_.~.~.~~.~~.~~.~~.~.~_<+_.~.~.~..~.................`_(++-______-.           `             `
..((++?===llltrrrrvzUuZy0Oz___`_~.``-jwZ<::~~~..~..(zzI<(zI<_.__..__~.~.~.~.~(>_..~.~..~._+z_~.~.~.~~.~~~.~~.~~~~~_1z_~.~.~~~.~.~................._?XXyz;<1z+++++(-. ``   `              `     `
zz=????=?=====lzzzwXXuvzXZI<<~_`` ..` (wZ<:::~~.....(yuZ<(v<~..-(~.~(<...~.~.~_<?_..~..~..~~+=<_~~.~~.~~.~.~~~~..~.~~(zz_..~.~~~_..~~................ (OWkwx(~<?1<<~___.-     `  `  `         `     `
????====1zzywXXyyWWWZuvwO<:____..-__-JwZ<;;;:~.....(zuzI=v~..._+>~._+<~..~..~.(+?_...~.~.~..<=z<~~~.~~.~~.~~.~~~~.~.~~(1z+_...~~___..~................._?zOO0Gx--__-   ` ` `   `       `
>??=zzrXVVZOOOrrttrvzXXWkkwOz1zzww++wyZz>+><~~~~.._+wuwI<_..._+=<.~(=<..~.~.~~(1z<..~.~.~..~(lz<_~~~.~.~~~~.~.~.~~.~.._<<zo_.~..~_<_.~~~......~_........-(1O<<?1z+-.__.     `     `
??==l==l=lllltttttOvwXpW0Oz?<+lzXSOOX0v>?=<~~.~...(zuuZ>_~~~_+zv~~~(l<...~...~(zl<.~..~.~~.~(1=<<~~~~~~.~.~~~~~.~~~~~~~(;+zz-..~~._<(~.~~~~..._~_........._?1-. _?1z--_.-    ` `     `    `  `   `   `
=ll====l=llllltttlttwXfWZ=?>>zIzwywwXI>+lz<~~~..._+wy0I<::~(+zt<~~_+I<~..~.~.~+zO<~..~~.~.~~_+lz<:~~~~~~.~~.~~.~~..~.~~~<?+zO<~~.~~_<<_.~~~.~.._:_....~__.._(1+. ` ~?1-.`_-     ` `     `
??=======lllllllllllwfy0z?>?>zzzuZXwVz>1l<~~~.~.~(zyyXOz;:<+OrI<~~(zI<..~.~~~_+rOz_~~~.~.~~~_+ll+;::~~~~~~.~~.~~.~~.~.~~~><<Ow<.~~~~_+z_~~~~~~.~_:_...-(<__.._+<.     ?<--  _-     ` `
>???=======l=l=l=lzdWW0I=????ztwuuuwI<1zI<~~~...~(wVy0I<:<1wvOz<_:<tI<.~.~~.~(zzOz<~.~~.~~~~~<ttz>;:~~~.~~~~~~~~~~~.~~~~~<<<<ww+~~.~~_1z_~~~.~~.~(;_...._<<_.._<+- `    _<<-  .       `  `  ` `  `  `
>>??==lllllll====zdWpSI??????zvzzzuO??ztv<~~~~.._jXVXZ<;+zwzwI<+z<<OI~~.~.~~~(zzOz<~~~.~~~:_~(OrO??<:~~~~~~.~~.~.~~~.~_:~(?<:+XO<~~~~~(1z<~~~.~.._<<_.~~._<=+___1z- ``    `~<_ .  `     `  `    `
wzzz==llllzzzzzzwXbpW0z????==wuuvuXv??OZ<:~~~~~~(dWpWO1zwuuzOzzOz~+vI_.~~~.~~(zzO=<~~~~~~_:_~(wrtl=+;:~~~~~~~~~~~.~~~._::(?<:(zzI<_~~~~(1z<~~~~~.~_<<_.~.~_<lz<__<z<.        ___-.`  `                `
fbWkkkkXWWpkkkkkqkbf0I?>??=lzwZuvwwz?zrI<~~~~~~~(dWbSrwwuuzzzuuZ>~jO>~~.~~~~~+wzOl<:~~.~~(>_~(wrtttz;<~~~~~~~~~~~~~~~~_;::;>;:<wwO<_~~~~(zz<~~~~~~~(?<.~~~~_+l=z--_1+__   `  ` `___.. `` ` ` ``  ` `
WWWWpppfppbkkbbbbbpWZ=?>>?=zwXyXrwO??zrI::~~~~~~+XbWXuuuuuzuuzzI:(zZ<~~~~~~_<+wzrlz<~~~.~(><~(wrttrO+<:~~~~~~~~~~~~.~~(>::;>><:1uOz<~~~~~<Oz<~~~~~~_<<_~~.~~_1l=lz_ <1<_   ``````  ___- ` `    `    `
ZXkXuXXXUWWpppppbpWZz??>>?zwWyZuOOO??zO<:::~:~~~+XSXXyZZuuuuXrO<:<wZ<~~~~~:(>1wztlz<~~~~~(?<:jztttrrz<:~:~~~~~~~~~~~~~(?<;;;?<:<OXOz<~~~~~+tz<~~~~~~(?<~~~~~~(1llz1- -<+--`  `   `   `_._   `   `  `  `
ZWkkbWkkXXZZyZWpbW0z????>?zXWUXXOl1>?OZ<~:::::((+XXVyZZuuuwZttv<:+wI<~~~~::>>1Ovrtv<~~~~_+=<(zXrttrrO<_~::~~~~~~~~~~~~(?;;;;>?<:1zOz<:~~~~(1lz_~~~~~~<z<~~~~~~(ztz=z+. <1+_ ``        `  _._.    `   `
XppppbpWXZuZyWWp0Z==?????zXbSOwyXz<>?zI::~:::;>?zXWWZZuuuZtltO<::jvI:~~:::;>?=tOrrv<~~.~(1=<(zwtttrrtz<~::~~~~~~~~~~~~+z;+<;??;:+wzOz<:~~~~(zO<~~~~~~(1z_~~~~~~<zO=lO+. _1z-.``` ``     ``  __- `   `
VpfpppppppWffWqHkl===?=?1wWHOlOXZXz;1wz::~::::<<1XZuuuuuZllltI<:<zOz:~:::<>>?1lzrrO<~~~~(lz<<wOtttttl=<:::~~~~~~~~~~~(+z>?z;>?>;+zvtlz<~~:~~+tz<~~~~~~<1<~~~~~~_+tOltO+.` 1O<_...`` `         ___. `
Wpppbbkkbbbppbkqkll=====zdWSOltrXuI>?w>::::::~::+wyZZZXZlllttz<:<zI<:~::;????=l1ttz<:~~~<lz:+tttttttl=<:;~~~:~~~~~~~~(zz>==???<>>zwrl=<:~~~~(ztz_~~~~~(z<:~~~~~~(1wOlrO< ` ?O<_<-   ` `       `  __. ``
kqkHWUUWWHHWWWkHSl==?===zWkkz=zvvrv?>z<:::::~:~(+wyZZuwtlllllz<:<zz:::(>+zzzzwzzwOzz<__(+O<;ztllllttl?>;<~~~~~:~~~~~:+Oz1zwwwwzzzzwvOl+_~~:~:+tz<:~~:~(1z:~~~~~~~(zrtrvO-`  ?1_-<<.    `` ``       __- `
WqWVtttttlttwWpWZ==??==lwWHkZ?1wuwz>;;:::~:::::<1wyZZXrttll==z::<zz<++zzrOzzOOvzwZz<~~~~1z<>ltllltll=?>;<~~~~~~~~~~~(1Oz<<1zzOOOZXXXWkw+_:~~~<zl?<:~~~:+=<~~::~:~~<zrvvzI-   ?1- _<-     `  `  `   ` ___
WUZtttttlltwWpW01??====lwWHWZ>?OuuI<;::::::~:~:<1wyZXrtlll=llz<(+wI?>>+1<;;>=?;+Oz<:~~~_+=??lllllll==?>;:~~~~~~~~~~__<==<(>????><<1zOOOC11+_::zl?<~~~~~<zz::~~:~~::+OzuuuI-`  (I--_<<-`     ` ` ` `   _~
rrttttttlOwWffSI===?===twppy0z>1XuOz::::::::~~~(zXZurtllzOltvz<<1z<;::<?<:;?=<:<zz<~~~~(??<>?==ll===??;:~~~~~~~~~~~~_<1=<(;????><:+=lltz_~~<::1l=z<~~~:(1O<~~~~:~~~(1wuZuuO-   (1<_._<_ ` `  `  `  `  `
tttttttttwWfWXZ=======lwXpfVXv>+zXXz;:::::::::~(zWXuOtrOz<<<::::;;:::;?<::;>><:+Ov<~~~~(??<;???===???>;~~~~~~~~~~~~~_(??<_<<???<<:<==llI<~~~~~+I==<:~~~:+l>::~:~::~:(zwXyuuO-   _<<..~_~_      `  `
tttttlttwXpW0OOll=====lwWbfyXI<>1wZZ<;::::::::~:+XWXwOz<::::::::::::;<?<:::;;::+tz<~~~~<?z<<>?===???>;<~~~~~~~~~~~~~~(??<~~_<??<__:<===zz_~~~~+z==?<~~~~<Oz<:~:~~:~~:<OXyWZuy-   _<_...~~_ `` ` ` ` ` `
ttlllttwXyW0I1ltll====OXqbWyuwz;>zXk>::::::::::~<dpkI;:::~~:~~:~::::;<<~_~~::~:<l<~~~~_+?<_<>??=???>;;~~~~~~~~~~~~~~~(??<~._(><~.__<?=?=v<~~~:<??=?<:~~:(zO>:~~::~:~::<zXfXZyw-   _<_~..~~~_     ` ` `
lttlltOXyX0<;>ztl=====zWqkWZuXz;>zwXI::::::::::::zW0I<::~~~~:~~~::::<~_....~~~~(=<~.~~(><__;>>????>;;<~.~..~..~.~..~~(?<<_.-(1z<___(>?==l<~~::>>+??<_~~~(zrz<:~:~~:~~::+wyyZZyI.    __.~.~~~_ `  `  `
lllttOwZXV<:;+lz=??==zwWkkWyZuI>>+wuI<::::::::::~(<!<1+_~.._~:~~~~~~~~__--__:~~(<~..~_+<_ (;;<???;;;:~~~.~~.~~.~.....(+++<<~_~~_` _~<1=llz_~~:><;??><~~~~zrI<::~:~~:~:::+XyyyySo_  ` __~..~.~~_ `    ``
llllOwZXZ>::<zO1???==zwWqqWVWuZ<>>wuZ<;:;;;::::::~:_ _11(....~~~_((+++zzz1<:~._(<_.~_:<_`.(<:<??;;::<~.~~.~~..~.~.~_+zv<~ ` .((---__:+lllz<~~(?<;??>><~~:+rI<:::~::~::::(zXyyyZXo_    _~~..~~~~_ ` `
=llzwZXV>~~:+tz????==zXWkkpfWXwz>?zuZ<::;;:;::::~:__` _1<~~.~_(++zwwkkkkkQQQQmAAz___:~_`._~~(??;;:::~............~~____-(J+gQWHHHHkmAwOl=?<~~(??;>???<:~:+rOz::~:~:~~~:::+wZXVyZuz_   ` __..~..~._  `
==lwXXZI<~:(zO>>>??=lwXWqbpppWkO>?1wZ<::;;;;:::::~~~ `` ...~(+zwwXWH@H@HHHHHH@HHkwz+<_.` ~._;<;::::~~....~........_` (&WH@MH@H@@HM#NMNkwOz<~~<?>;:>??;::~<OzI<~~::~:~~:~~<zvzXyZuw+_     ~_..~~.~.. ` `
==zXZVv~~~_<zz>;;?=llwXHHpbbpfWXz??zwz:;:;;:;:::~~~__```.__(zwWWWHMMHH@@@@@MMMMHHWWkk+_...._:<::::~_.............``.JXH@@@@@@HHKUWMMMMMHkwz<:<??>;>??>;:~(zvO<~~~~:~:~~:~(zrrwXWuzw+_     __..~~~..._  `
==wZ0I<_.._+z;<++zzOwXWmHHHpppfXOz?zrz;;;;;;;:::::~_..`._(+dHMMMMM#HH@@gHMMHHWUWHH@@HRz__.._~~~::~_.........`...`` (Xgg@HHHHHHHNk+<zWMMMHWXz<<=?>;;>??;;:(zvOz_~~~:~:~:~~:+OrtwWXXzO>_     ___..~~.... `
=zwXZ<:~_((zwX0XWWWWqpWH0XfpfppWkz=ltz;;;;;;;;::::~~~.._(dMM###HH#HHHHMMMNNNMMHy<?WHMHkx_..~~_:::_..```.. ```..`` (XH@HHHHHHHHHMNk<_<wHMHHXZO=lz>;;>??;;::+wzI<:~:~:~~:~~~<1OOlwXZzrO<_- `  _:_.._~_....
OwZV<::(uwXWWC<dWHWkqWWpVwWfffppWZlltz>;;;;;;;;::::~~~_(dMMMHHHH###NNNMMMMMM#HMK>~~?7UUZ<_.`` _:_..``` ._``. _```(XHHHHH####H###MK<~(zWmqWXO=llz?;;;>>;;;;+wzOz~::~:::~:~:<?zwOzwuXttz_(_-    _~_.._~_..
zX0v:~:<?XpWC~(dHHWWkWXWZwXfpffpfkOttz?;;;;;;;;:::::~(+dMMMMHMNNNNNNMMMMMMMMY=?<<_~~___<~```` ~~_```..~~.`.._ ```jHH@HHHNNMN#MH9U6<~(jXHHSZz1ztz>;:;>?<::;+Ovvz<~::~:~:::::+z1wzzwI?zl<__<_.`  _<__  _~~
XXC<~~~~~+W0<(dpp0wXpWyyZzXfpVfppWXrtz?>;;;;;;;;:::::<zWMMMHMMMNN#NNNNMMMMNl      ...```````` ~_.`..-~~....`    `dHHHHH#NMMMMD~``  _(zXWUVOz1wwz?;:;>?<:~<zwvvz<~:::~::~:~:<1<1XOtI<_<?<_____    ~<__.~.
XC<~~:~~~<zOzwVy0zjXpWyZZzwWpffpppWXOz?>;;;;;;;;;:::;+zWMNNVMMNN#HH####MMMMR+. .. `.```````` ~_....__ .... `  ```dH@HHMMMMHHHR-. .-_(d0I+1t=zwwl?;:;>?<::<zvzzI<:::~~::::::(1z<OXtr>- <+_-._~_    -~:_..
+<:::~~~~+wXyyW0>(dfpVZZZ+zXfffpppWkwz??>>;;;;;;;;;;:;>vHMNHMM#M@H@H@MMMM@@gHmQXkc `````  `` .....   .~._    ` ` zHHmqkkkHHMHMHkWH0?OX>_(1l=OuXO>;;;>?>::<zuuzOz<;<~~:~:::~:<zz<zvtI_` <1_.._~_     _~~_
:~::::::~+XpWUC~_(XppVZuZ>1wWppfpppWkI??>>>;;;;;;;;;;;;;zWMHNMM@mmgqmqqqqg@@HHHHH>  ` `    ``.``     `      `    jWWHgqkkqqHHHHggHC(z>` (==zwuXI<;;;>=>;:<zZzzuOz<<~:::;<:~::<?<<?Ot+-` <?<_`_~_-``   _~
~~~::::::<wV>~._(zfpfVVXZ<<zXffffpffWXz>>>>>;;;;;;;;;;;;>+ZMMMMHHHkkkkkqqHHHUuXWC_     `` ` ````    ``     `  `` (yIzWWHkHWUC1dHM$~_<``.+?zwZuuZ<;:<?=?<:+wZrwZuXz<::::;<:::::>?< <=z< ` <1<-`-___ `
~~::::::::<<_._+zwppfyUXX>~<wyVyWUUUuuO?>??>;;;;;;;;;;;;;;;1WMMHSZVUWWWWUUVCzXV0>   `           `      `  `  `  `(Xk-(?7C<<__(X@@!`-~`.<?=wZZZ0I<;;+==z:(zX0rwXuuwz:~::;<~:~::;<<_ <=<_`  <=<-.__~__ `
~~::::::::::((+=OXVfW0wXXc__1XW0<<zwuZXz>????;;;;;;;;;;;;;;;<dMMRI?zOOz<;<+jwXSC`      `   `     `  `   `     ` ` jWXA&+++++udHY! ` -(<<_jXZZuzO=<:+=l<:+wZZOXXzzzz<~:+><~::::;;;_ .1z<.   (1<_..~~~_
_~:::::::~:~zuI<dXW0ZzwuuI_`(zwI::<OuZuI??==?>;;>;>>>>;>>;;;;:<?Tz1zzzzwwkXXWW0! ` ` `  ` `   `    `  `  ` `  `  ` ?UWWWWWWWH6!`` ._~`` (dyyXzrwv<:+lt>(zZ0IOZXvvuw<:(?<:~:~:::;;_  (=z<    _<1--._~~__
_;;:::::~~~<Oz+XW0v<zuzuI_`-(1z<:<zuZuwz?=llz>;;>;>>;>>;>;;;><_._<OXWpkqqHHkWI!``` `` `     `  `    `  `   `  ` ``` ~?7TU9UC<_.._ ``` (jXy0ZtwkI<(+rI<jwXI?wZXvuuZo_(?;:~~::::;;_   +1<_     ?1<_...~_~
_(;>::::~~~~(wOzW0<++rwvuI_` _<?<:<zwuZXI?=llz?;>>>;>>;;>;>;;>>>_. (zWWkHHH9Y>_````` ` `` ``      `  `   ` `` ` ` ``````````...`````` _(zX0IzwWWI:(zXv(dy0<+wZuvuuZZ++?;::~~~::<;<-` (?<~  `  `_<<-_..~~
(;;<:::::~~~_zXwZ<<+=ttruI_. _(><:<1wuuuOz=lttz>>;;>>>>>;>;;;;;><_ ` _<<!_````````````` ``  `  `    `  `  `  ``  ` `````.....~~__....~~<zXOzdWWS>:+wZ<jXSz;+wZzzuuuXlOz<<~:~:~~:<<`   <<_-       _<<-...
<>>?:::~:~~~~+XZ<:+z=ttvuI_..~~;><;zwZZurtlltrOz>>>>;;>>>>>>;;;::;<.``````........``````` `  `   `    `  `  _  ```````.....~~~::~::::(:+wZOwffZ0>(z0I1wX0<;+wZzzuZXrOz;><:~:~::~(<    (?<_       ` ~<<_~
?+?z::~:~~~~~(zwz:<t=trruI_..._(><+zwZyXwtllrrvOz>>>>>>;>>;>;;;:::<<- ``.`.........`````` `  `  `  `  `      ` ` ``````......~~~~~~~~:<zzzwXXyXZ<+XZlzXyI:;+wuuzuyXI1<;><_~~:~~:(< `   <>< `         <;_
l1=z:::~:~:~~:<wXz<11rrrw0<.``._<1wuuXXyXwtlwzuzwz>>>>>>>>;>;;;;<~~<<__``..`....`...`````` `   `    `  `` `   `  ` ``````......~~~~~~~+wwI11wuZI+dSOwwy0>:<1OuXvuZXI<;;>?<:~:~:~::     (><   `         ~
lllz::~:~:~~:~(zXkz<1zvrw0<_.`` (wZuzzzXXXOlOuuZuwz?>>>>>>>;>;;;;<_~~<<_```````.````````   `  `  `   `   ` `  ` ` ` ````````........_(zXI<>+wzOzzuXwuZXC<<+<1wZXzZZwz;;;?<:~~:~:::      <<.    `
tttz:::~:~~:~~:+wZ0zzwuOwI<__`.(zZXzvvzzuyWwtwXZZuwzz?>>>>>>;;;;;;<_.._<_.``````````````` `  `    ` ` `    ` ` ` ` `````````````````-+wI1<<(vZlOuuzzzu0<:+v<<zZuuZuzI<:<+<<~:~~~::      (;_       `
rrrz::::~:~~::::zw0OOwuOtZ<__-(zZuvrvvzuuuyWwtwXZZuwOz?>>>>;;;;;;;><_.. _~_.``````````  `  `  ` `  `  ` ``  ` ` ` `  `` ```````````.(zZ<<<_jXrOzwuzvzXC<(zz<;+wuuuzzwz<:<=<:~~:~~;-     (>~
vvvz::~::~:~~:~:<zrrwuuIOtz<(jwVzzzzzzzzzuuZZXrvXyZuwOz?>>>>>;;;;:;+<_.`` _~_. ```````   `   `  `    ` ` ``    ` `` `` ```````````.(wXv;<++zzI<(wzrvX0<:jzwO<(OwXuwrrl<::<=<~~~~:;_     .><    `   ` `
zuZ<;:::~:~:~~::;?ztuXXIlrOz<<~_?CXuzzzvvvzuZZXvvXyyXXOz?>>??>;;:::<z<_ ` `  __-.  `  ``  ` ` `` `` ``` ._`` ``  ` `` ``  ` ```` .jwXZz1zv1OI:_(zvvvuI~(wvwXo:<1wZXrOz<::<+<~~~~~<_`     <<       `
uuZ;:::~:~:~::~:<?lrXykIzwXI!     _?XuzzvtOwXuuuzzXXyXXwOz?>>>>;;:::+1<_-       `_..``  `  `   `  ` `` __`` `  ``  ` ` ``` `` .(+wXZZ=ztI~(l>`.zzzzXZ<(zvuuXk+:~+wXvOz<::::;_~~~:<<`     (<     `    `
uuI;::::~:~~:~::;>zOuZXI=wuI       ` ?OzvrtzzwuuuuuwXWWXXvOz+>;;;;;:<+<<__   `             ` ` ``  `    `  ` `  ` ` ` `  ``.(JzrzuZXOlv<_(zv~`(wuzX0>(jrOwuzuZ<~_?XXrI<~:~::~~~~~<<`     .<.   `    `
zZz::~:~~:~~~:~:;?zwuuXv=Ow>           ?OwOO+<1OOXuXrZWfWXuuwz+;;;;::<++<~_``         ` `   `  ` ``  ` ` `  ` ` `` ` ``` -(zwzvvvvvzZ>_ (+<_` (zzzZI+zrtllOrwzI<~~?XXt<~~:~~~~~~~<< `     :.
zZ<:::~::~:~~:::;+zruuuI=tr>    `        ?1OOz<_~<?XXOzZWyXuZXwO+<::::<1+__-  `` `  `    `    `  ` `  `  `  ` `  ` `` .(zwuzzvvrrrvuI<.(<<_``-jvvwIuwuzvtlzttwrz<_~?Xwz<~~~~~~~.~<<_` `   (_ `   ` `  `
OI<:~~~~~~~:~~::;1trzuuI=trz                ??1z_  _?XOzzZUuuZZZXOz<:::;1z++(--.  `  `    `` `  `  ``  ` ``  ` `` .-JzXZZZuzvvvrttOOI<::~_ ` (zrrI+XWXrrrz1OlOwrz<__?Xw+:~~~~~..~(<_      (_
O<::~~:~~:~~~:~:<zttvuuOltrI_`   `  `        ` _~`   _jwz?zOOOOXXZXOz<;<+wwOl=zz+--. ` ``   ` `` `` ``` ` ` `` .(+wXZZZyyZuzrvrtOv<<<~:_ ```.jttv! (XXrtrO=ztltrwz<_.?OO<:~~~.~..(<_`   ` (~   `    `
z<:~~~~~~~~~~~::+lltwXzzOtwZ<`        `         `      _1OOz====zwXXzwz1?zz<<1===llzz+-..  ` `  ` `` `` `` ..JuXZZZZZZZyyXwrvvrO<~(<_ (_ `` (tlv!   ?XXtrrO=l=llrrz<_._jwc_~~....(><  `   ~`     `    `
<:~~~:~~~~~~~~:(1lltwWvvvrww<`  `       `  `      `      _<1<+1lllllOwOz??1wAzzOzzlllltlzz+-..```` `` ` .(+wZyZZZZZuuuZyUvrrvrO<_-(`   _   -zz<!     ?uwrzO===lttttO<_._?OO<~...._1>      _   `
::~~~~~~~~:~~~_<==ltXWvvvrww<`    `           `  `  `       `__~?zllll=?>;<zWHHHHkkkkkAwwwwOOz+++J-...(+wZZZuuuuZuXVOXuXrrrrOv!``._     `  (z<`       jXrvzO==ltrrttI<_._(1z<_~.._+>. `   `       `  `
:~~~~~~~~~~~~~(+=llOXSuzzrwZ: `     `                ` `       ` _<+1=??>::<OWHmggmmmmmggHHkkky_jMMHHWWWyuuuuuuuVC<<duXrrttv<~ ` _       ` :~     `  `.OXrvzO=lwzvrrtO+_.._<<<:__~<z_`   `   `
~~~~~~~~~~~~~~+?=llwyZuuuzwZ<`   `     `     `          ` `       ` _<??><:~<zOOUWHkkkqmmg@HUWS<.XM@gqkpW0OwzvZI!` (XXvrrOv!   `    ` `    _           (wXrvzO=Ozvrrrttz<_._~_.__~+t<   ``  `  ` `  `  `
~~~~~~~~~~~~~~<?=ltXyZuuuuuZ~`           `     `  `         `       _(<>??<~~(1+-._<?77TUWHHOzw<.(WHHY=<!+udky-...JdwOz<!`  ```  `   `    `         `   (wwrvzI=OvrrrrOtO+-~~_...~_(<_.` `  `     `
~~~~~.~~~~~~~_+==lwXWZZZZuuZ~  `   `                   `  `   `  ` .`_~;;<><_~(zOz<:~___.._~<<1< `_<<-  .dH@gmqHHHHHkkkmAwa&&&&&&+--....         `       ?wrrrOz1OzvrrvOtOz-____....._<_. `  `  `    `
~...~~.~.~~.~(?==lwWWyZyyZZI_         `   `  `      `  `   `  ` .(__`` _~<??+_~_<1=<_~~~~~~~~_(<_   (1z+dWgggmmmmmgggggggg@@g@@@@HMHmx_~<+-.   `     `    (OrtrO++OzvrrzwOlO+_~(<-......_~_.   `  `   `
~.~~.~~.~~.~~<?==lwWpyVVVyV:    `                   `   ``` .(+Qk>``  ``-~<==1+_~~(<<_::~~~~~~~+<  ` (OXWmggmmmmgggggg@@@@g@@@@@@H@HHHA- _1Xme..  `        (OOrvI<<zXwrrwzOzzO+__<+--......_~_.   `  `
~.~~.~.~~.~~(+==llwWppppW0>        `     `  `  `  `  `   .jdHMHHNn-  ` ``_~<????<_::<;<:~~~~~._(z-    (XHggggggHg@HHMHMMHg@@@@@@@@@@@HHHo- ?XHHR-   `      `_Ozvwz::<zXwOtwXz+OO+_~<1---......__~_.
~.~.~~..~.~~(?=llOwWbHUYC!     `                `     ` (dMHHHHHHMHm&..```__<???>;:::::<::___-(dWm+. `.wWg@HMMMMMMMMHHWHH@@@@@@@@@@@@@HHNm- (dHMk-   ` `     .jzrO<::~?OuwrwXw+?OO+_(+=++-........___-.
~.~~~.~~.~~(+=lltwXW0!``             `  `    `   `` ..JdHHH@H@@HHHH@HHme...__<<<;;:::~~._.   `?XH@@He..jWqmHWpkHqqHHM@@@@@@@@@@@@@@@H@@HHMk<`(XH@Ho.    `    ` 1Xwz<:~:<1XXwrwuwz1Oz<;+1l1+-_........._.
~~~~.~~~~.~(1lllrzXC`         `   `      `  ` .(J+gQHHHH@H@HH@@@@@@@@@@HHm+ `.__~<<~_~...``` .(WH@@@@@MMHgggHHHMMMH@@@@@@@@@@@MHMMHM@@@@HHMR< (WH@Hk-    `  `   ?wwz_~~~:<zXXOOwXXOOz+<<+zlz+-..~~~.....
~~.~~~.~~~_<zltrruC`     `  `    `    `   ..JuwWHHM#H@@@@@@H@H@H@@@@@@@H@HC ``. `       _..(iqHHH@HH@@HHHHHHHH##HH@HHH@@@@@HHMMHqkkm@H@@@@HMk- zWgqqko.          (OOz_~~~::<zXwttOXuuuXwz+<+1=+-.~.~~...
~~~~~~~~.~(+ttrrvZ!  `         `   `` ..JgqHMMMHHH@@M@@@@@@@@@H@@@H@@@H@MS!```  ` ...(+gQWHMMHH@@HHHHHHHHH###NNN#HHHHHHHMMM@HHHkkqqHH@@@@@@HMm-_OWmqkHk+  `  `    _zOz_~~~~;<<OXwttrrvzuuuwz+;<1+-~.~...
~~~~~~~~~~(zrrvzzI`   `    `    ..(JgQHH@H@@HH@HHH@H@@@HH@@H@@@@@@@@@@@@HC_``` .(dQHHH@H@HHHHHHH#HHHHHH#HMM##NNMMMMMMM@HH@@gmkkqqg@HH@@@H@@HHMn-(XqmqkqHn-    `    _1l+_~~~~<<:?XXrttrrrvvvzzwz++1<_~~..
~~~~~~~~~~+trvzuuI   ` ..(JJJ+gQWH@@@@@@@@@@@@@@@@@@HHHH@HH@HH@H@@@@H@HMf!.`..iXH@H@H@@H@H@HHHHH@HHHH##MHUWH9UWHHkAzXWHHM@@@HMH@g@@@@@@@@@@@HHNo_(Wmmqqqqk&.    `   _1l+_:~~:<?<<?XXrrrrrrrrrrwvwz+<~~~~
~~~~~~~~~(1tvzuuu>  .-uXpfpWHH@@@@@@@@@@gg@g@g@gg@@@@@@@MHHMHHH@HHHH@HMD<_-(dH@@@@@@@HH@H@@@@@@@M###NNNM6zU0I__?XWHgHkkZOTHHHH@@@@@@@H@H@@@@@HHN>_wmmqqkkkHk-        (1==<_~~~~<+_(?wwrrtrrrrtrrrrvO+_:~
:~~:~~~~~(zrzuZuu>_(+wuXXXWHM@@@@g@ggggg@gggggggggg@g@@@MKZvTTUWWHHHMM9>_(dM@@@@@@MMMMMMMMM@HHHHH####NM$~<<<~ ` _<zUWHHHm+(??TWHHH@H@@@@@@@@@@HMR-(Wmqkkkkqqkx.`      (?==1<~~~~(<+_~?VzOrrrrrrrrrrrvwz+
:~:~~~~~(+zrwuZZX<<+zrrvXWH@@@@g@gg@g@@@@g@@gggg@gg@g@@@MHI<::::::~__.``-dMH@@@@@HMky<<??7UHHHHHH####M$__<;___``` _?OUWHMMHm&-_?7UWH@@@@@H@@@@H@HI_jHqkkkkkqkHs-   `   <=?1z+_~~~~<1+_~?zwrrrrvzwwwvrrrz
~~~~:~~:(llvuZZZV<+ztrrwW@@ggggg@g@@@@@@g@@g@@g@g@gg@@@@@HXw&++++<<____(+XVUWHM@@@HH@HA+-_+XMHHHH###MH:` _<<+<   ``` _?1VWHHkWk&.  ~?TWM@@@@@@@@@R<_ZHqqkkkkkkHn_      -+===lz_~~~~_+Oz-~~?zOvrOOOVXXzzr
_:::~~~(1ltwuZyyZ??ltwXH@Hgmmgg@@@@@@@@H@@@@@@@@@@@g@@@@HMWZXZZuzOl==11dW0z?1zwWH@@@@@@HkwwXHMHHH##HM0_````-~~   ` ```` <zXWUXWHHkA+-.-(zWMM@@@H@NI_(WqkkkbkkkkHl       (????=<~~~~~~(Owz<~~<zOvOz?11zrX

*/
#include "bits/stdc++.h"

using namespace std;

template <int p>
struct Modint
{
	int value;

	Modint() : value(0) {}
	Modint(long x) : value(x >= 0 ? x % p : (p + x % p) % p) {}

	inline Modint &operator+=(const Modint &b)
	{
		if ((this->value += b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator-=(const Modint &b)
	{
		if ((this->value += p - b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator*=(const Modint &b)
	{
		this->value = (int)((1LL * this->value * b.value) % p);
		return (*this);
	}
	inline Modint &operator/=(const Modint &b)
	{
		(*this) *= b.inverse();
		return (*this);
	}

	Modint operator+(const Modint &b) const { return Modint(*this) += b; }
	Modint operator-(const Modint &b) const { return Modint(*this) -= b; }
	Modint operator*(const Modint &b) const { return Modint(*this) *= b; }
	Modint operator/(const Modint &b) const { return Modint(*this) /= b; }

	inline Modint &operator++(int) { return (*this) += 1; }
	inline Modint &operator--(int) { return (*this) -= 1; }

	inline bool operator==(const Modint &b) const { return this->value == b.value; }
	inline bool operator!=(const Modint &b) const { return this->value != b.value; }
	inline bool operator<(const Modint &b) const { return this->value < b.value; }
	inline bool operator<=(const Modint &b) const { return this->value <= b.value; }
	inline bool operator>(const Modint &b) const { return this->value > b.value; }
	inline bool operator>=(const Modint &b) const { return this->value >= b.value; }

	//requires that "this->value and p are co-prime"
	// a_i * v + a_(i+1) * p = r_i
	// r_i = r_(i+1) * q_(i+1) * r_(i+2)
	// q == 1 (i > 1)
	// reference: https://atcoder.jp/contests/agc026/submissions/2845729 (line:93)
	inline Modint inverse() const
	{
		assert(this->value != 0);
		int r0 = p, r1 = this->value, a0 = 0, a1 = 1;
		while (r1)
		{
			int q = r0 / r1;
			r0 -= q * r1;
			swap(r0, r1);
			a0 -= q * a1;
			swap(a0, a1);
		}
		return Modint(a0);
	}

	friend istream &operator>>(istream &is, Modint<p> &a)
	{
		long t;
		is >> t;
		a = Modint<p>(t);
		return is;
	}
	friend ostream &operator<<(ostream &os, const Modint<p> &a)
	{
		return os << a.value;
	}
};

const int MOD = 1e9+7;

using Int = Modint<MOD>;

void solve()
{
	int N;
	string S;
	cin >> N >> S;
	//dp[i][j] := using j-th number in rest in turn i
	vector<Int> dp(N, 1);
	for (int i = 0; i < N-1; i++)
	{
		vector<Int> nx(N-i);
		if (S[i] == '>')
		{
			for (int j = N-i-2; j >= 0; j--)
			{
				nx[j] = nx[j+1] + dp[j+1];
			}
		}
		else
		{
			nx[0] = dp[0];
			for (int j = 0; j < N-i-2; j++)
			{
				nx[j+1] = nx[j] + dp[j+1];
			}
		}
		swap(dp, nx);
	}
	cout << dp[0] << endl;
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 256