ჭიანჭველების დათვლა

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

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

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

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

წყარო: USACO, 2005/06, NOV, SILVER


ბუბა აკვირდება ჭიანჭველებს. მან  შეამჩნია, რომ ბუდეში იყო T (1 <= T <= 1,000) განსხვავებული ოჯახი ჭიანჭველებისა, რომლებიც მან გადანომრა როგორც 1..T. თითოეულ ოჯახს ყავს Ni (1 <= Ni <= 100) რაოდენობის წევრი. ჯამში სულ A რაოდენობის ჭიანჭველაა.

თქვენი ამოცანაა დათვალოთ რამდენი განსხვავებული S, S+1, ..., B (1 <= S <= B <= A) ზომის ჯგუფი შეიძლება შედგეს ჭიანჭველებისა.

მაგალითად თუ ბუდეში არის {1, 1, 2, 2, 3} ჭიანჭველები. მაშინ შესაძლებელი ჯგუფები ჭიანჭველებისა არის:

 

3 ჯგუფი 1 ჭიანჭველით თითოში: {1} {2} {3}

5 ჯგუფი 2 ჭიანჭველით თითოში: {1,1} {1,2} {1,3} {2,2} {2,3}

5 ჯგუფი 3 ჭიანჭველით თითოში: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}

3 ჯგუფი 4 ჭიანჭველით თითოში: {1,2,2,3} {1,1,2,2} {1,1,2,3}

1 ჯგუფი 5 ჭიანჭველით თითოში: {1,1,2,2,3}

შემოსატანი მონაცემები: პირველი სტრქონი შეიცავს თითო ჰარით გამოყოფილ 4 მთელ რიცხვს T, A, S, და B. შემდეგი A ხაზიდან მე-i შეიცავს ერთ ცალ მთელ რიცხვს, იმ ოჯახის ნომერს, რომელსაც მე-i ჭიანჭველა მიეკუთვნება.

 

გამოსატანი მონაცემები: თქვენმა პროგრამამ უნდა დაბეჭდოს რაოდენობა ისეთი განსხვავებლი ჯგუფებისა, რომლის ზომებიც არის S..B. თუ რიცხვი დიდია, დაბეჭდეთ მხოლოდ ბოლო 6 ციფრი.

 

ყურადღება მიაქციეთ, რომ ჯგუფი {1, 2} და {2,1}  ერთდაიგივედ ითვლება.

 




მაგალითები

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

შენიშვნა

შეტანის განმარტება: ეს ნიშნავს, რომ არის 2 ცალი პირველი ოჯახის წევრი ჭიანჭველა, 2 ცალი მეორე ოჯახის წევრი ხოლო ერთი ცალი მესამე ოჯახის წევრი 

და ჩვენ ნდა ვიპოვოთ ისეთი ჭიანჭველების ჯგუფების რაოდენობა რომლებშიც არის ან 2 ან 3 ჭიანჭველაროგორც მაგალითზე ჩანს, ეს არის 10.