ტკბილეული

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

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

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

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

წყარო: GEOI, 2010, შესარჩევი


მშობლებს, რომლებსაც M რაოდენობის შვილი ჰყავთ, სურთ საშობაო დღესასწაულზე ბავშვებს საუკეთესო ტკბილეული უყიდონ. მათ შეარჩიეს კანფეტები, რომლებიც ლამაზ სამკუთხა ყუთებშია ჩალაგებული. ყუთის პირველ მწკრივში 1 კანფეტია, მეორეში – 2, მესამეში – 3 და ა.შ. მაღაზიაში, სადაც ისინი ტკბილეულის ყიდვას აპირებენ, გაყიდვაში აქვთ კანფეტების ყუთები მწკრივთა ნებისმიერი რაოდენობით 1-დან N-მდე. ქვემოთ, ნახაზზე ნაჩვენებია ყუთი კანფეტთა 5 მწკრივით და 15 კანფეტით.
 
                                                                                   #
                                                                               #     #
                                                                           #     #     #
                                                                       #     #     #     #
                                                                   #     #     #     #     #
 
    იმისათვის, რომ რომელიმე ბავშვი გულდაწყვეტილი არ დარჩეს, მშობლებს სურთ ისეთი ყუთი შეიძინონ, რომ მასში არსებული კანფეტების რაოდენობა მათ შორის თანაბრად განაწილდეს და ყუთშიც არაფერი არ დარჩეს (ანუ, კანფეტების რაოდენობა მთელად იყოფოდეს M-ზე). თუმცა, ამ შემთხვევაში ისინი სხვა პრობლემას გადააწყდნენ: ისეთი ყუთის შეძენის შესაძლო ვარიანტები, რომელიც ზემოთ ნახსენებ პირობას აკმაყოფილებს, საკმაოდ ბევრი აღმოჩნდა და მათ რომ შესაფერისი ყუთი შეარჩიონ, აინტერესებთ თუ არჩევანის რამდენი ვარიანტი არსებობს.
    დაეხმარეთ მშობლებს და დაწერეთ პროგრამა, რომელიც მოცემული N და M რიცხვებისათვის დაადგენს კანფეტების ყუთის არჩევის მათთვის სასურველ განსხვავებულ ვარიანტთა რაოდენობას იმ ყუთებიდან, რომლებშიც მწკრივთა რაოდენობა იცვლება 1-დან N-მდე. ვარიანტები განსხვავებულად ითვლება, თუ მათ შეესაბამებათ ყუთები მწკრივთა განსხვავებული რაოდენობით.
 
    შესატანი მონაცემები: შესატან მონაცემთა ფაილის ერთადერთ სტრიქონში მოცემულია ერთი ჰარით გამოყოფილი ორი მთელი რიცხვი: N – ყუთში კანფეტების მწკრივთა მაქსიმალური რაოდენობა და M (1 ≤ N,M ≤ 2 *10^9) – ბავშვების რაოდენობა შესაბამისად. 
 
    გამოსატანი მონაცემები: გამოსატან მონაცემთა ფაილის ერთადერთ სტრიქონში უნდა ჩაიწეროს ერთი მთელი რიცხვი – კანფეტების ყუთის არჩევის განსხვავებულ ვარიანტთა რაოდენობა.
 
ტესტების 35%_ში N, M ≤ 1000
ტესტების 55%_ში N, M ≤ 10^5
 
 



მაგალითები

შესატანი მონაცემები
20 10 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება
შესატანი მონაცემები
53 199 დაკოპირება
გამოსატანი მონაცემები
0 დაკოპირება
შესატანი მონაცემები
5705 145 დაკოპირება
გამოსატანი მონაცემები
157 დაკოპირება