Օրանգուտյան

Իմաստուն Վարպետ Օրանգուտյանը հասել է գիտակցության բարձրագույն մակարդակի և ունի առարկաների գեղեցկության մասին խորը գաղափարներ:

Արմատավորված ուղղորդված ծառը այնպիսի արմատավորված ծառ է, որտեղ բոլոր կողերը ուղղորդված են արմատից դեպի տերևները։

Օրանգուտյանը ունի երկարության հաջորդականություն, որը հանդիսանում է գեղեցկության հիմքը:

գագաթանի արմատավորված ուղղորդված ծառը գեղեցիկ է, եթե բավարարված են հետևյալ պայմանները․

գագաթները համարակալված են -ից թվերով,
համարով գագաթը արմատն է,
համարով գագաթից դուրս եկող կողերը քանակը հավասար է թվին։

Ավելին, գեղեցիկ ծառի համարով գագաթի ենթածառի գագաթների քանակը (ներառյալ -ն) նշանակենք -ով։ համարով գագաթը գեղեցիկ է, եթե ։

Ըստ Օրանգուտյանի, կյանքի իմաստը հասկանալու համար անհրաժեշտ է գտնել բոլոր իրարից տարբեր գեղեցիկ ծառերում առկա բոլոր գեղեցիկ գագաթների քանակների գումարի մնացորդը -ի վրա բաժանելիս։

Երկու ծառ համարվում են տարբեր, եթե տարբեր են նրանց կողերի բազմությունները (գագաթները համարակալված են)։

Մուտքային տվյալներ

Առաջին տողը պարունակում է թրվը՝ հաջորդականության երկարությունը ():

Երկրորդ տողը պարունակում է թվերը ()։

Ելքային տվյալներ

Պետք է արտածել մեկ թիվ՝ բոլոր գեղեցիկ ծառերում առկա բոլոր գեղեցիկ գագաթների քանակների գումարի մնացորդը -ի վրա բաժանելիս։

Oրինակներ

Մուտք	Ելք
4 1 0 2 0	1
4 1 1 1 0	2
7 3 1 0 0 1 1 0	36

Oրինակների բացատրություն

Առաջին օրինակի միակ գեղեցիկ ծառը հետևյալն է (միակ գեղեցիկ գագաթը համարով գագաթն է)․

Երկրորդ օրինակում գոյություն ունեն երկու գեղեցիկ ծառեր (այս ծառերի գեղեցիկ գագաթները քանակը համապատասխանաբար և է)․

Ենթախնդիրներ

Համար	Սահմանափակում	Միավոր
0	Օրինակները	0
1		21
2		21
3		11
4		1
5		22
6	Լրացուցիչ սահմանափակումներ չկան	24

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB