SPOJ in Armenian

Հաքիմին ունի N հատ օղակ, որոնք նա համարակալել է 1-ից N թվերով: Նա նաև ունի N-1 հատ պարան և ցանկանում է այդ պարանները օգտագործել հետևյալ նպատակով:

Նա կարող է վերցնել ցանկացած երկու տարբեր օղակ և իրար միացնել պարանով (օղակները միացվում են պարանի ծայրերին):

Վերջում բոլոր օղակները պետք է լինեն կապակցված (ցանկացած երկու օղակ պետք է միացված լինեն անմիջապես պարանով կամ ինչ-որ հաջորդական պարանների միջոցով): Այսինքն՝ այն պետք է ունենա ծառի կառուցվածք:

i-րդ օղակին պետք է անմիջապես միացված լինեն ճիշտ ai պարաններ:

Ձեր խնդիրն է հաշվել՝ քանի եղանակով է հնարավոր միացնել օղակները պարաններով, որ բավարարվեն վերևի երեք պայմանները (ըստ 109+7 մոդուլի):

Մուտք

Առաջին տողը պարունակում է N բնական թիվը (2≤N≤105): Հաջորդ N տողերից i-րդը պարունակում է մեկ ամբողջ թիվ՝ ai -ն  (1≤ai≤3): Թեստերի 50%-ում N≤1000:

Ելք

Ելքում պետք է արտածել այդ քանակի 109+7 -ի վրա բաժանելուց ստացված մնացորդը (ոչ բացասական ամբողջ թիվ):

Օրինակ

Մուտք.

9
1
3
2
1
3
1
2
1
2

Ելք.
1260