ბალანსი

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

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

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

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

წყარო: GEOI, 2010, რეგიონული, X კლასი


 

საბას უცნაური სასწორი აქვს და სურს იგი წონასწორობაში მოიყვანოს. სინამდვილეში, ეს მოწყობილობა სხვა სასწორებისაგან განსხვავებულია. 

მას გააჩნია ორი მხარი, რომელთაგან თითოეულის სიგრძე 15-ია (მათი წონები უმნიშვნელოა და მხედველობაში არ მიიღება). ორივე ამ მხარზე მიმაგრებულია კავები (საკიდრები) და საბას სურს ჩამოკიდოს მათზე საწონები თავისი  G რაოდენობიანი კოლექციიდან (1≤G≤20) იცის რა, რომ ამ საწონებს გააჩნიათ განსხვავებული წონები 1..25 დიაპაზონიდან. საბას შეუძლია ნებისმიერი საწონი ნებისმიერ კავზე ჩამოკიდოს, მაგრამ მან აუცილებლად ყველა მათგანი უნდა გამოიყენოს.

საბამ მოახერხა სასწორის გაწონასწორება, მაგრამ ახლა მას აინტერესებს, რამდენი განსხვავებული გზით შეიძლება ამის გაკეთება.

დაწერეთ პროგრამა, რომელიც კავების მოცემული განლაგებისათვის და საწონების მოცემული წონებისათვის იპოვის სასწორის გაწონასწორების განსხვავებულ გზათა რაოდენობას.

გარანტირებულია, რომ ყოველი ტესტისათვის იარსებებს ერთი მაინც ამონახსნი.

შესატანი მონაცემები:  პირველ სტრიქონში მოცემულია ერთი ჰარით გამოყოფილი ორი მთელი დადებითი C და G რიცხვი (2≤C,G≤20) – კავების და საწონების რაოდენობა შესაბამისად. მომდევნო სტრიქონი შეიცავს თითო ჰარით გამოყოფილ, ზრდადობით დალაგებულ C რაოდენობის განსხვავებულ რიცხვს -15..15 დიაპაზონიდან და ისინი კავების განლაგებას გვიჩვენებენ. ყოველი რიცხვით წარმოდგენილია კავის პოზიცია სასწორის წონასწორობის ცენტრის მიმართ X ღერძის გასწვრივ (როცა სასწორზე არცერთი საწონი არ არის ჩამოკიდებული, იგი გაწონასწორებულია და X ღერძის გასწვრივაა მიმართული). პოზიციის გამომსახველი რიცხვის აბსოლუტური მნიშვნელობა წარმოადგენს მანძილს კავსა და წონასწორობის ცენტრს შორის, ხოლო მისი ნიშანი განსაზღვრავს სასწორის იმ მხარს, რომელზედაც ეს კავია მიმაგრებული: ნიშანი '-' ნიშნავს, რომ კავი მიმაგრებულია მარცხენა მხარზე, ხოლო ნიშანი '+' კი - მარჯვენა მხარზე. 

მომდევნო სტრიქონში ჩაწერილია ერთმანეთისაგან ასევე თითო ჰარით გამოყოფილი, ზრდადობით დალაგებული G რაოდენობის განსხვავებული ნატურალური რიცხვი 1..25 დიაპაზონიდან და ისინი საწონების წონებს გვიჩვენებენ.

გამოსატანი მონაცემები:  ერთადერთ სტრიქონში უნდა ჩაიწეროს ერთი მთელი M (1≤M≤2,000,000,000) რიცხვი _ სასწორის გაწონასწორების განსხვავებულ გზათა რაოდენობა.

სასწორი გაწონასწორებულად ითვლება, თუ საწონების წონების მათი პოზიციების შესაბამის რიცხვებზე ნამრავლთა ჯამი ნულის ტოლია.




მაგალითები

შესატანი მონაცემები
2 4 -2 3 3 4 5 8 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება