### BUGGY CODE ###

'''
z<<~``_<<<<<<~    `  _<+zlvzOOwrvvvvvzzzzzzzzzw)`              ``<:i.``.XC~(>~~.~.~.~.~.~.~.~.~~~(~~~.~~~.~~~~~~.~~.~~.~~.~~~~~~~~~~?-~(WZZX\..`..J<;;;<_```.``..(XZyyyyyyyyyyyyyyyyyyyZyyyyyWX0OIlwXyyV
:_- ` `   ``       ` -~~~~~__<1Orrrrrrvrvvvvvvr\`` ` `  `  `    `?<(>`..C(<~.......~.........~..(:...~...~..(............~.........~~(I~?SuZ..`.->;;;;!.``.``...-duZyZZyyyZZyZyyyyyyyZyyyZZyZZXXwwXyyyyy
::<_ `  ``````````` ``````   _<1trrrrrrrrrrrrrtl`   ` `  `  ` `  .` ?_ J(!..._```   -`````` . ..J--...~._-...-..   ````````   ```_...~_1_(k%.`.(<;>;<_...!```..(wuZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZuZZ
   ````````````````` ...--(++++ztttttttrtrtrrttz`  `   `   `   ` . ``~(/` ```````  ._..~.~_J~~.(>~~~~.~~<~~~(:~.~~~~~......  ````````  _1_?{...<;>;_--?!``....(UzuuuuuuuuuuuuuuuuuuuZuuuuuuuuXOOOC7<<+1O
`  ````````.......-_(<?=llllltttltttttttttttttlz``          `  `` <-..'```` ..+_.~({~~~.~_jl~~(z~~.~.~~_z~~~_$~~.~.~(-~~~.~~.~.._.. `````_.<..z;<+?!_````.`.(JrzzzuuzuzuuuuzuuzuuuuzZOOwwOOwwO<_~. ``` _
`````` __(___-(+++zz1+zlllltlllltlllllltlltlltlz `` ` ` `    `    _..!.--..~(z>~~(v~~~~~_+w~~_jZ~~.~~.~(z~~~~v-~~~.~(z_~~~~~~~~~~.__.._.. (.;(+?~.`.`.....(ZtrrvvvvvvvvvvvvvrwrwrrrOz<<<!__~<?1z<~.````.
_-.   -__:_(<>??=lllllllllltlllllllllllllllltllz_        `    ` ``i(>~(~~~~_jt>~(zl~~.~_jCc~~(Z>~~~.~~~(z~~~~>1~~.~~_zz_~~.~.~~.~~~<~~~~~~~1j<..``.....JOltttrrtrrrrrrttttOz<<<1OOz<~ ``     .__.. . ..-
1++++++1=======llllllllllllllllllllllllllllll==z_` `  `   `     ` <<~(<~~.~(tt<_jw~~~~~(C(>~(d>>~~.~.~~(l<~~~<(:~~~~~zro~~~.~~(~~~~(<~~~~~~~Cl-.-(+z<~?1+1llllttlttlttllz<<~`__~<<<~ ``-(<<<_(((++++++zz
l============l==l====l==l======================?}`  `  `   ` `  ` (~~c~~~~(trO~(tr~~~~(C_.~~jr~>~~~.~~~jt>~~~(~(-~~~~jvrc~~~~~(;~~~_z_~~.~~~(I.`.`.`_<-~_T=11<<1=l==z<<<<_-.. ```...`  _(<+++ztttttOOwwv
==?===?==?=?=?===========?=??=?==?=??????=???=??l`            ` ``.~(:~.~~jrrI(Owl((Juf^!???U=1c~~~~.~~jrI~~~(- j-_(((Xwvx~~~~~l~~~~z>~~~~~_~j_.```.`. ?-(I><:(>???>?++++++?+<(((((((++++zOwrrrrvzvvzuuX
????????>???????>????>????>????>??>???>??>?>?>>>z`` `` ` `       `.<J~~~~(OrvI(wd3~~_v```.~(}` (~.~~~~~jrr<~~~}`_1<~~~TXUUVOJ-~1~~~~jI~~~.~>~_n--..`.``.-1j???????????=?=???===lzzOwrrrrrzuuzzzvwrrrrwXX
?>>>>>>>>>>>>>>>>>;>;>;;>;>;;>;;;>;;>;>>;>;>>;>;+`    `   `` ``  ` 1t~~~~(rvzIwvd:~~J`  `.~J```(<~(~~~~(rrG_~~<`` ?-~~(JXzvc~_?z-~~~jr<~~~~(~~j>+1,.``.``-1I?????????????=zzzOrrvvrrzwzzuXZtrrwwvwtrrrrr
Ozllzzzzzz+<>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:(.``   `    `  `` `O>~~.~jvzzAkzd~~(!`  `._:` ` l~(_~~~(vzvI~~(. ``(-~~1(Uvrx~~(>~~~zrI~~~~(x~(><<<1..`.`.-4>>>?>????zzzwwXuuuuuXvvvwwrttttttttrOrwwwwXX
XkwwwwOttrrOOzz+++++<;;;:::;:;;<++zzzzzyyzzz++<;(_ ` `  `        ``(<~~~~zvzuXkzX:({`` ``.( `  `(-~l~~~(OzzZI~~>`  `.<~(/_4vvc~(>~~~zvI~~~~_Z+~}.. _<i.`.`.(I?????1zwzuZZZZZuwrrvwuwwwwwvrrttrvzzvzuXWpb
pWXuuuzzvrwzuXXXXkkkkAwz+++&zywwuuZyXZZyyyyVyWkw&)`   `  `` ``  ` `._~~~~zzzuXkXU<J```  ..$-..`` 1~(/~~~jzvw.l~(.` `` <_(._jvvo~l~~(wzO_~~~~I1~>.````._ ``..(zzOwwwuZZZXXwZOrrrXZXZyyyXZuvrrrvrrwXyZXWfW
ZyfWXzuzvrtrwXyZWWWWWUWWWWWWXyyyZZZyyZZZZyyZZZZy3:```  `   `  `  `  :~~~~zzuuXkd(AmQQQgggggg&J-.`.:(I-~~(vvw_ 1~> _~!!!?+1. ?yvOl~~(vzv<~~~~dA;>.``.````.``..1rzzzuuuXzrrrttttOrwXZXWpW0ZrttrrrvwyVfWkWW
kbfyXXuuwrtttOwwrXuuzzwXXWHbbbWWXXuuuZuuZXXZZZWXXR``  `   `   `  ```<~~(:zzuzXk$-Z_~(Y!?HHHNv?? ``.->(-~~zvr}` <(JmQggga&gm--Jkvr~:jzzv<~~~~zzbz...`.`.```.`.(XzzzXzrrrvvvzwwXXXwXWWH0VrtOwwwXXXWWWWWpfH
qqqkkHkXXXXwwwOOwOwrvuuuuuXXXWUUXXXZyyZyZXXZZyyyXz ` `  `  ` `  `  `-~~j_jzzuzR>```.Wo..H@@@L``   `.J_.<~(wrw```?u_(=~?MHH@YYYYWl:(vzzv>_>~:dzXwn,..``.``.``..(OrrwwzvzuuuuyWkkkXWkHWXwwXWWWWWkkkqmmmmHq
qmqkbbbpppfyZurrwXXXwrrwu0XXXXvvuuXwuzzzXUUXZZyyk(_`  `  `  `  `   `._~d2jzuuzX~`  .kmyHHHVHb``  ` `.1 `~-(rd-``` 1qo.-MM@Mb  `.<(zXuzv<(>~~wuXKw<<-..`.`.```..jXXWWWXyuvrwXWWbWWkHWWWWWWkqHHHHkkHHHHmgm
WWWWkbWWWWpWXuZXXXVWXXXuwrttrrXZZZyVyZZyXkXzvzXX$~{``  `  `   `  ``  l:wW+zXkzd_` `,kHSWHMOXP` ` `  ` ! ` <?tl` ``,qRWHHMHgK```,_Jduuuv<J~~~kuXSuI~~~?<-.....`._WWHWUVrrwXXWWWWWkqmHHHWbkkpfyyfbWWWbbHqm
pWWWpppWWVfWkkwuXWpkwOtrwOwvwOOrwXUWpWXuXyXZZZXX<~<` `  `  `   `   ``(-wRhOuWuv|``  zHZwXwXf! `   `     ` ` ?O<` `,HZdHH@dqD`` >JwSuuzf(W_:(Suuuuv:~~~~~~~_<<+--(kXXXwOwXUWWHkHHHHWUZyWpWWppVVWWHkqmmmgg
qqkbbbpfVVfyyZZ0ZXUUUuuXXZXuvuuXXXuXWffWWWkXZZXr~~(.` `  `  ` `  ` ``.XzWuWXXHvG``` `?4kkkV^`  `       `  ````_ ` .HZXswdXC```,jdSuuuXCJW:~JzuuuuzI~~~~~~~~~~(0wWHW0ZtOwwwXyWWWZXWWWWWkHWyyppWWWbkqqHggg
ggmHHqqkkkbpVyuvrwzzzuuyyZuuuuZXuuuuZyyWWkHWWXXl~~_;` `    `   `  ` ``UWXkuWkh?yl``` ``````` `  `` ` `   `    `  ``.4kXXXY!``.XCduuXW0jHH:(Suuuuuzv<~~~~~~~~~(0tXZXXkwXWVXZtlOwXWbpWkmggHHWHmmggmqmHqHHH
gggHHHWWWHWUUuZuuuzuzXXZZuuuZyyWXZZZuuuZyWbkkWK:~~~>`  ` `  `   `  ` `(dHWXuXWL(4,```````` `` ``  `  `  `  `  ` ``````  ` ``.v!JzuXWRuSWX:dzuuuuuuzI~~~.~~.~~~0rXWHWqHHHWXrtttwWgH0VWHHWHHH@@@HWUVWHgHXX
HHHUUuZyyXzuzXZZZyZuuXwXZZuuXVVXXZZZZZZyfppfWW$~~~~( `  `  ` `  `   ``.WZwHuuzU!` ``````````` `  `  ` `  ` ` ` `````````````` JvXXXKGSZdDJXuuuuuuuzw<~~~~~~~~~dXXkmggHHHUVtrrwXWqHkzlllzwWpHggHkz?1ZWHWW
VwXkwwzuZXXXkZOXVWuuXXZ0VXuuuWWuzzuuuuZyWWUWXX:~~~~_;``      `  ` `  ``1I:?OzzZ;`````````` ``  `  `    ` `  ` `` ` `````````.JZ=kuWX0>:(dSuuuuzuuuuvc~~~~.~~~~Jqqqmg@HWWkXwvvwWH@gHwOOwwWqgggg@Hkz>1zwWg
XrXWW0OOwXpWSwzvXXzwtwwwOwuXXwZVOOOvzuuXkXrI1$~~~~~~1` `` `   `  ` ` ` (0+~~(zvX.`````````` `` ` ` `   `  `   ` ``````````` !`.vwWSZ:~(dpKuuuuuuuuzzI~~~~~~~~~(qmmgg@HWUUUXZOXWqg@HSOOXWgg@@@H@HHkzzXWHg
tlOXXkXXZyyfWXXuuzzuXwzzttOrOzzzzzOwwuwWKIz<J<~~~~~(z-`  ` ` `  `  ` .(^/(~~~(rrl````` `` ``  `   `  `   ` ` ` ``` ``````````.c~kzzZ~~((WHuuuzuuuuuzv<~~~.~~~~(KWWHg@gH0rrrrwWqH@@HSOwWg@@HHHHHMH0Z=zwUW
kOlOwXSZtrOXXwtltOOOZXUXwtOI1zOZUWWyyyWHHkmAf~~~~~~(r$.`  `  ` ` `  __c/`.l~~:jrw<``` `  `  `  `  `   `   `   `  ``````` ``` J~(RzzI~~~(WWuuuuuzzuuuvI~~~~.~~~:WfbkHH0XrwZXkXWH@@@HkXWH@@HHHHHHMHkkXXXXw
kwwwXWWkkZOvzz=lOOzwuuXU0OOOlzzzzzwWWHkHH@MH>~~~~~(zvw-_ ` `  `` .._>.!`.:1:~~(Ovv-` ` `    ` ` `   `  `   ` `  `     ` ``` JJdWSuzI~~~(WWkuuuzuuuuuzO~~~~~~~~~dWUU0XZwXZ0XWH@@qmH@gHZWH@HHH@M@@@HWyWb0T
HHWWH@@@HkkXwwOOvzz1l=11z++zywZuUXWHMHHHHHMK~~~~~~(zzu$~~_....-.~~(J(!`.::(?1_~(vrO.``  `` `     ` `    ``  ` `  ` `   ``` J+zwXuuzI~:((qHHuuuuuuuuuzv<~~~~~~~~(vzzOOOwwkkWUWm@@g@@HWWWHHM@MMHH@@HWfp0z+
ppWHHHMHHHHXzwwOzzzwwXvrrttOOOllOwXvXH@MHMH$~~~~~_zzkXv-~~..~~.~~_},~`.~~``>_(-~jvvn `` `  `  `   ` ~   ~ `    ` ` `` ``` JwwXWHuuz>~~z(qmHuuuuuzuuuzzI~~~.~~~~(kuuuOXWpWW0wUWWUWWHqHMMHHHHWyvOUUUUWWwmg
WyVpkmH@@@HWWWbppbkH0ZOrtll=zl=?zdHHHMHHHMH>~~~~~(zu$?:3~~~.~.~~/./ `.~~``.>.`.:~jzzS+.``` ``  `      `    `  ` `   ``` .dWWkHg#uuv>~:I(mgHKuuuuzuuuuzO:~~~.~~~~WUUUWWHHkwOlll=zrwWHM#HMHWWQsz+WkwWHWHkH
WWpHqqHm@@HWWUUXuzvvwwwyXwOtlllOwXHMMHH@H@@:~~~~~jzuX+_?/~~~.(<?<!` _~_`` /.. `,-~OzX2+Oi. ` `` ` `    `  `  ` ` ``` .(CzzOWHqHHuzw<~(IJggHHuuuzuuuXuuv<~~~~~~~~z+(+zXWgHWXkkwOllwWH@MMMTHWWWRWMGkVWQgMM
wXWH@@@@H@HkkWfWUUUVOOOzz====zwXWHHHH@M@@MC~~~~~(wuu$o:1j-~-(:./``.~:_ ` /` .-``<~(wzXOlllzO-. ` ` ```  `` `` ` ..Jzz++zOzzwWWHSuzI~~(:dHHHWXuuuuuuXuuvc~~~~.~~~(k++wXWHHXWHHkwOwXMHMmx1Zz1A+WWHMmgydHHM
XWqH@@H@ggHHWVyXkXwwwwOwzzzuwXH@H@MHHgHMH#:~~~~~(zuzX-?+3 1!./``._~~```._`` ._``(~~(zuWvrrtO:~_<<..` `` ` ..-<<(Illllll=llllOZWuzv>~_Z:XUUXZRuuzuuuXKuzI~~~~~~~~(HkWpWWyWWWWqHkXWH@HM@MHHQwWHWWZWHNHMMMM
wXH@@@@@@@HXXkXZZV0UUUUUUUWHMHH@MggHqqHH@$~~~~~(Ozuuzk--_<!! ` _~:_ ``.!` ``. ``._~:jzXkrttl>~~.~.~?<<~?<~~.~~~jllltlllllllttzKuzZ:~($($?ztlXzuuzuuuHuuv<~~~.~~~~dHHHWZyWWpWH@HHmHHHWHqMMMgMNAgMM@MMNNMM
WWHHHHHgHqqkWWXwOltttrrttzzWHHHmqqg@H@@HM>~~~~~(vuuuz%4<?+-.._~~_``` ,!`` ``. ``.<~~~OuWyCCz>~~.~~.~.~.~.~.~~~~jltttttllltttzdUzvC~:vr(IzzlzvkzuuuuuXuuv>~~~~~~~~JHHHWWWWHggHM@HmmHVTWpWWMMMMMMBWMMMNWMM
WHmbfWmg@HHHWfWXXXXwOOwXXwdWHHHkqHHHHHH@@:~~~~~zzuuuw:.{_<<=<:~````./``  `    ``.l(_~(vZ2<~~1-~~.~.~~.~.~.~...~jltttttttttlO?dzzO<~(H$JyZXOz+XuuuzuuXkuzI~~~~~~~~(HHHHHHH@@@@MHMmHWx>v7UZuWK6+zwQHM@@HdM
VWHWyWHH@@@@HHWpWU0ZOOXWWkXHHMHH@@HH@MMg3~~~~~(vuuuvZ`` !-~~~..`` .!`` `` ``  ``.j-l~~jr$`~.`.<_.~~.~.~~.~.._``.v<<1z<1?==zzdSzzC:~dWtkWppfffWkuuuuuuHuzO_~~~.~~~~d@@@@@@@HHHHHH9U+vCjgkkHV>_((dMDZH#Mkd
HMMHkWWWg@H@@@@HWkwwwkWWHHH@@H@HHHM@HHgK:~~~~~jzuuzv%```` _<<--(->_`` ` ` ``  ``.~C1(_(Sd_` _.`.<-~..~.._` `` `` 17!`?1wzXXZKuuZ<:(WWwHHWWWWWWHuuuuuuWuuv<~~~~~~~~?HqmH@@mHWyyXI?<jodkdY=<(uaxdHHMMMMHR=
HHHMHWWH@H@MMgqHHHqqqqHHMMHHHHgHHH@@@@g$~~~~~(wuuuzw!```` ...~.... ` ` `` `  ` `.~(J_<:wr[``` _.` !. ` `   ` ..?~```` ,!?1wwSuv>:(SvddvrrvrrrrdkuuuuuXKuzc~~~~~~~~~dqkHHHHHHkHHkkXy>?I?jnJ+d@HMMMMBXXHWH
H@HHHWgggggHH@@@@ggqkbpbbSwUUWHMMHHHHMH<~~~~~(zuuuzZ``` `..~..~..`` `` ` ``  ```(.~O>>~Jk$ ```  ~.`` !-..._!``` `` .,!````.dzzC~(ZtrXSrrrrrttttWuzuuuuHuzI~~~.~~~~~?0OOOz1<<1OWWqH&z+WmHHmW@M#BXXmazdMHH
@H@MmmHHMHHHHHH@@qkbWfppWI<1dWbpHHHHHHD~~~~~~jzuuuvI`` ` ...~..~. ` ` ` ` ``` ``(._(c<~(SI_`  ` ``_-.`````````` ..!  `` ``.0zZ<(<?7CHOrrrrrrtrrZkuuuuuXkuw<~~~.~~~~~Owwz><?<?1zW8HHWqHMHMM@MM&,(dAdMRW6z
HH@@gg@@MMMMHMM@@HHHHHWHHkwwWppfXWWgHW>~~~~~(wzuuuvI``` ` ...~...` ` ` ` ` ` ` `<.`.r<~((l_`` `  ``.<<-.. ..._!```  `  ``.kzwI(>```.! ?OttrrttrrXuuuuuuHuzc~~~~~.~~~?kkWAZOdHmkkdMMHMgMHHHHNezXHWM91jdSW
HHHggHMHHWUUWWWH@@@@@@@HWWyWWZWkqqHHHP~~~~~~(zuuuuzw-```  ..~..~.`` `` ``  ` ```:_` $<~<(r  `` ` `` <....... ``  ` ` ``` Jvw9(:``` :````?OtttttrwHuuuuuWuzI~~~~~~~~~~XH$ZIdHHOMMMNgMMBTM@HQZ<(NNNK++nJd#
@@HgHXXVwvrtwuXWHqHH@@gHVVWWyWWHHpfyX>~~~~~~zzuuuuuvG.```` ..~... `  ``  ` ` ```> ``I+_{.\` ` ` ` ` :.. ._:_`` `` ` ````(rZjJ!``  `  ` ``.ItrtrrrdkuuuuXKuw_~~~.~~~~~(ugd0U6Vz1JM@HWMejgMHHNHMMMHHHMHHMH
gH@HHVtlOXXXXpWHH@@@@HHqbbkXWWH@@qkHD~~~~~~(rzuuuuuuwn.`` ` ..~.._`` ` ` `. `   :`` Iv(`-```  ` ` ``>._ ~(_ `  ` ` ` ``,Z^(< ``  ` `  ````.OrvzwrrWuuuuuHuz>~~~~~~~~~(XnzWBWmyWRdQMHH@94WH#I<?TIdYWRzUXH
qqHWVwXXXfpbbkH@MHmkWWXXWHHMHHH@HHWXC~~~~~~(zuuXuuuuuWH,```` ..~__ ` `  `  ` `` !``.1I>`_` ``` ` ` `:. ..>_`` ` ` ` ``.=.?!``` `` ` `` . ``(rrzuwrwWuuuudkzI~~~~.~~~~~zWH@MMM#MM#MM90vO=dMmmgHmdH96<zuvW
ffW0rwXuZyyZWHHMgqqbWXXXWHMMMHHHHZXf~~~~~~~zzuXSuuuudHHMe.``` ..~>_`` ```  ` `` _``(z=```    ` ` ```<.`~(>`` ``  ` ` `` ````  ` ` ` ` .~```.kvzuXwvdkuuuuHuw_~~~~.~~~~?VHHM4WMmdMMMMNdMkqXMHB7TUOwueWMMM
pWpWXXOwuX0ZwXWWHHHHHHHqH@@@@HHWyWWC~~~~~~(vzuXuuuuXMHHMHS, `` ..(. `  ` . `   `` .=```  ```` ` ` ``(_ .(_``  `` ` `   `  ` ` `  ` ` `.` ```OrzuZuvrXkuuuXXz>~~~~~~~~~~wWWHHMNMMMMMNMgM#NM#M9+<1vY61dWMM
HWHSOztrrtlltwWHMMM@H@HVWMHM@HkkXWP:~~~.~~(zuXSuuuuWHHHMHXZo-`` .(-_```  .  `` ` ````` ` `  `  `   `.` ~>`` `  `` ` `` ``  ` ` `` ` ``:`  ``jrvzuZzvvXXuuXRzI~~~~.~~~~~(QxWsdHMMMNMMMNMMMMNoz6<zC+-(jdMW
@H0C<1ltvOzzUOZOXWWHHHgH@HHHMMggqq>~~~~~~~jzuXuuuuXMMHHU0XXkk,.`_~>._` ` .`  `` `   `  `` ` `` `` ``.  _> `` ``  ` ` `  `` ` ` ` ` `` :`` ``(rvzuZuzvvWXuuWuw_~~~~.~~~~(STMMM#NMMNMHM9TM871J~j+.?UkHNgS&
MSZlttI1ztzwrwOI+zVUuWH@HMHHHXkHHK~~~~~~~(wzuKuuuXHHHWHHHkH@HHh--~(_. ``._` `  ` ``  ``  ` `  ` `  ` . (_`  ` ` ` ` ` ` ` ` ` ` ` `  .` `` `.rvzzuuuvvzWuuXKzc~~~~~~~~~~dnH#NMNMMHM9<<_dWyqWgxCXkzzdMNH@
0OOOrzwvzOOC+OrOzuyXwwXkkkXXWXXUX3~~~~~~~(zuXSuuudHH@@HH@H@HHHMHe__l._` . ` ` ` ` ``  `  `` `` ` ` ` _-( `` `  ` ` ` ` ` ` ` ` ` `.``.`  ```.4vzvvuuzzvuHuuWuO:~~~~.~~~~(MMMMMMHMMMHHR=<dNWMSjHIgdMQMMMM
wyOCzOXWXwttvz+OXyWUkO+?wkAwXHyfK:~~~~~~~jzuXuuuXHmggggHHH@@H@H@HNJj_.` . `  ` `   ` ` `  `  ` ` `` `:.;`` ` `` ` `  ``  ` `  ` ` _``;``  ``.<1vvvXyuzzzXHuXkv<~~~~~~~~~(SX9WXWM#MM6WmgdMS3jHHY<udW9TNgH
HkXW0I&zZC1jQkQ0>+1zvwZk<dWUHXXX3~~~~~~~_zuuKuuudg@@@@g@HMHHH@HHH#HNc~_ .```  ` ``  ` ` `  `  `   ```<_}`` `  ` ` ` `  `` ` ` ` ``~`.! ``  ` : 1rvwXuuzzzXHZHz>~~~~~~~~~~z>(dNHMMHRWN#HHKddHK<<(Z1z&dHD<
kzZ1OXCwzjwXWXXI(zwwAwZwv<+XHHXK:~~~~~~~(zuXRuuXH@gmHHHH@@HHHHMM#NNHN__..`` `` ` `` ` ` ``` `` ``  ``((:``` `` ` ` ` `` `  ` `` ``_`.`` ```` :``jXwrvuXXkuXHWXI:~~~~~~~~:J4HHMMNdMMNXMMHM@D<?1XWHHmHHMHH
'''


import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int,input().split()))
p = 10**9+7
used = [-1]*n
for i in range(n+1):
    if used[A[i]-1]>=0:
        a = used[A[i]-1]
        b = i
        break
    used[A[i]-1] = i


#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

######################################################


#pは素数とする

#fact[i] : i! modp (0<= i <p) O(p)
fact = [1]
k = 1
for i in range(1,n+2):
    k = k*i%p
    fact.append(k)


#n! = a p^eとしたときのeを求める (O(logp n)
def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res

#n! = a p^eとしたときのa mod pを求める  (O(logp n)
def mod_fact(n,p):
    if n==0:
        return 1
    
    
    res = mod_fact(n//p,p)
    
    if n//p %2 != 0:
        return res*(p-fact[n%p])%p
    return res*fact[n%p]%p
    
######################################################

#nCk mod p
def mod_comb(n,k,p):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p
#print(a,b)
for i in range(1,n+2):
    res = mod_comb(n+1,i,p)-mod_comb(a+n-b,i-1,p)
    if res < 0:
        res += p
    print(res)

### FIXED CODE ###

#<` _!~`    (?<?OrvvvzzzI`       .(. C/~.~..~..~.(~.~.~_~..~.~~.~~~<-4X~..<;!.``.-XyyyyyyyyyyyyyXwwXy
#~~```````   ...+trrrrrrI`   `    `_(!`  ` _ .._-:..~-.~_....  `  ``__C..;<_.~`..uuZZZZZZZZZZZZX00VT0
#  ` ...-((<zltttttlttttl      `  ~(_ .(>_<~~(c~+~~~_:~(~~~(~~.~..-.  -.<<!.`..JvzzzzzzzzXZC17?C1- `
#---((++zllllllllllllllll. `     `<<<~(z<J<~(v>(C~.~(l~(<~~(o~~~~~(_~~(+...(+zOttrrttv<!<1>` .._----(
#=======================?_  `   ` <(~~jO(Z_(c((y(~~~(I~(_<~(wx~~(~~l~~~( ``.<(v<<111<-(-....(++zOwwww
#???>>?>>>>?>>>>>>>>>>>>>:`   `  `(>~(wZz$~/  (`.__~(r+~!_<~OXZ>(_~z_~(~C-.`.(z??????=1zzOrwwwVwzvrrZ
#wOwzzz++<;;;;;;;++++++<:: `      .<~(zXkr(`  -` ><~(ww-~  ~(?zx(<~z>~(l<_<_`.-+??1zwwZuVzzvOrtrwvwXk
#WkuzrZXyVfWX&swXZXWZyWWkI`  ` ` ` _~(uuZG&..(o-..(:~zz-_...~<(Oo<(wI~~z(.`._``(wzuXUwrrwXXWWVrrrXWXW
#HkkkwwOOwXuuXWHWyXXXZZZyV`   `   `<((uuI(`2-MM/``_<<(r;.jTYWHRwk>(zI-~wG,````. OwzvwwXXkdWHrwXkWHkkW
#HkWWWXwwWXwVwXwXXXXXUXU3_`    ` `((2Xk% .HdMX\   .._(l``dndMN .(wuI<~XWI<-...`(XW0UwwWpWqqbkHHWHpHg
#WWbpfWWXUWXwwwwwwXWkXXZ0~:` `  `  .xWwWO``?kwf     `  ?!`zXMWY`(duXG$(uuu:~~~_<&jWZOXWWHWWXWWWWWHmgg
#gHHHkHUXwuzXXuXXXXXUWHk$~(  `    ``dWXWz{`````` ``      ` ?"= .CuXDd$duuuI~~~~_wXkkWSOzdHWHHHHHHHHHW
#UUuUXXkXXXXXXuXSXXZXpWW<~(.`  `  ` -v4ur```````  `  ` `` `````.ZXXVjwuuuuz<~~~~XWgHHkwwWgkluXWgHzzUW
#ZXXydWkwuwwOwVVOlwuXSIv~~_;`   `   ,C~(w-````  `     ` ``````  (XZ~?fuuuuul~~~~dHHMk0wdq@HOW@MHMHZwH
#kwXmwOOOtzwZwOzvwWkWNk>~~(w-` `  ./!.>~jn `   `   `      ` ```(JkZ~(pXuuuuI~~~~(WHSwwWWHMNKHMHM@HWWk
#HHH@HkuOlzyzzwZVXUMMM#~~~zXl~__~_<!.~(<_Ol` `  ` `   `  `   `(uXuI~+mKuuuuz<~~~(zzwkp0WHHHWkHMWHMWW&
#WWqHMHHWUU0wOzlzdHMHHD~~(zI(_~__~~._`__-(wS-.`  `  `  ` `  .vWHHuC(zgHuuuuul~~~~V7UHkAwzwWMMHWmdWHWH
#dH@HMHWWXwOzzzdqHMMMM<~~ju2(>-~_ __`. .`<?Xytw<.. ` ` ..+llzOwUHu>((HUkuuXXI~~~~jaXHWWHwXMNmmddVNmHH
#XHMHHHWkOwVVVUMMHHHM@~~(wuZ+-_.-~`.~``.`<~jXZt<~.~~<~~~(ttttltOSZ~zj1zUuuuWz<~~~?MHXWWMMHHWHMMNHMMMN
#WHWH@HHkXXtXkXMHHMHMt~~(uur-_<<``.!` `` (+(w>_~_~~.~.._(vzvzOzdzC(RkkAdXuuWul~~~_HH@@MMM961dwf<zKMNW
#MMHWMHMHkQWH@MMMH@MK~~_yuz!` _<<! ` ` ``_1_(l``.~__`  `..! ?OXSZ_dSUUUUSuuXkI~~~~JqHHkkk+vOC+JmkMMHX
#HMg@MMMMHHHbRvdHMMMt~~(uuZ`  .~._`  ````<(<(0 ` `. ````` .```,w>?OKrrOOdXuuWw_~~~(wv<?zXHmdMMM#79WWW
#m@@HHHHH@HHHHwWWWHH<~~(uuw ` ... ` ` ` `! I(1_``  _~__~   ``.XZ~`. (zrtrWuuXu>~~~~jk0dHNHMMMH91HH1VX
#HWrXWWWHHHWXHMMMHX<~~(uXuudh.` ._ `     `.v``` ` `< (``` ``!_ ` `   `.wwwdXuWw~~~~~wHMMMMNmsdN#WSigg
#WK0OVOwWMMHHMMHkWD~~~juSuXHMK+  (_``  ` ``` ` ` ` ~ <`  `  `` ` ```~ `OzZzXuXk:~~~~(V9WNMMNM##Z+v<XM
#MI+vzzzZTWHHMMMHH<~~_wXuZWHkkWm,.< `.  `  `  ` ` `_.~ ` `` ` ` ` ` ` `jzXuzWZWI~~~~~wMMMMM5ZnsJGJWNQ
#XOOwwOzOdkwTWUWWr~~~(uXuXMMMMHHMm(_`_ `  `  ` ``   (` `  ` ` `  `_.```(wvXuzWXk_~~~~dMMHHMM&N9Q8WHMW
#UVwOIjk0+zwU?4kX<~~~(uWZHHMMHHHMMNc-_` `` ` `   ``._`` `  ` ` ```__ `  .OZXXXWR:~~~~(uWMHHM#mV3&QQMQ
import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int,input().split()))
p = 10**9+7
used = [-1]*n
for i in range(n+1):
    if used[A[i]-1]>=0:
        a = used[A[i]-1]
        b = i
        break
    used[A[i]-1] = i


#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

######################################################


#pは素数とする

#fact[i] : i! modp (0<= i <p) O(p)
fact = [1]
k = 1
for i in range(1,n+2):
    k = k*i%p
    fact.append(k)


#n! = a p^eとしたときのeを求める (O(logp n)
def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res

#n! = a p^eとしたときのa mod pを求める  (O(logp n)
def mod_fact(n,p):
    if n==0:
        return 1
    
    
    res = mod_fact(n//p,p)
    
    if n//p %2 != 0:
        return res*(p-fact[n%p])%p
    return res*fact[n%p]%p
    
######################################################

#nCk mod p
def mod_comb(n,k,p):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p
#print(a,b)
for i in range(1,n+2):
    res = mod_comb(n+1,i,p)-mod_comb(a+n-b,i-1,p)
    if res < 0:
        res += p
    print(res)