ლამაზი მწკრივი

დროის ლიმიტი: 3 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: cin

გამომავალი მონაცემები: cout

წყარო: IZHO, 2012


ალი-ამირმა ამოწერა N ცალი რიცხვი ერთ მწკრივში. მწკრივი ითვლება ლამაზად, თუ მასში შემავალი ნებისმიერი ორი მეზობელი წევრის ორობით ან სამობით ჩანაწერში ტოლი რაოდენობის 1-იანია. ალი-ამირს აინტერესებს, რამდენი განსხვავებული ვარიანტი არსებობს ისეთი ლამაზი მწკრივის მისაღებად, რომელიც ყველა მოცემული N ცალი რიცხვისაგან შედგება.

შემავალი მონაცემები : პირველ სტრიქონში ერთი მთელი რიცხვი N (2 <= N <=20). მეორე სტრიქონში N ცალი მთელი დადებითი რიცხვი, რომელთაგან თითოეული არ აღემატება 109 (მილიარდს).

გამომავალი მონაცემები : ერთადერთ სტრიქონში ერთი მთელი რიცხვი: მოცემული N ცალი რიცხვისაგან შედგენილი ყველა ლამაზი მწკრივის რაოდენობა.




მაგალითები

შესატანი მონაცემები
3 5 1 6 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

მაგალითში 5 = 123 და 1 = 13, 5 = 1012 და 6 = 1102, ამიტომ არსებობს ორი მიმდევრობა: 1, 5, 6 და 6, 5, 1.

 

ტესტების 25%–სათვის N <= 4.

ტესტების 50%–სათვის N <= 10.