ფრისბის გუნდი

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

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

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

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

წყარო: USACO, 2008/09, MAR, SILVER


ფერმერ დონის შემდეგ, ჯონმაც გადაწყვიტა შეექმნა ფრისბის გუნდი. მას სურს, რომ
ჩამოაყალიბოს გუნდი თავისი N მოთამაშისაგან (1 <= N <=2,000), რომლებიც
თანმიმდევრულად არიან გადანომრილი 1-დან N-მდე.  i-ურ მოთამაშეს აქვს  რეიტინგი
R_i (1 <=R_i <= 100,000), რომელიც უჩვენებს მისი ოსტატობის დონეს.
 ჯონს შეუძლია ჩამოაყალიბოს გუნდი ერთი ან მეტი მოთამაშისაგან.
 
გუნდის დაკომპლექტებისათვის ჯონმა შემოიღო ერთი დამატებითი პირობა. 
რამდენადაც მისი საყვარელი რიცხვი არის F (1 <= F <= 1,000), ის ქმნის ისეთ
გუნდს, რომლის წევრების რეიტინგების ჯამი ზუსტად იყოფა მის საყვარელ F-ზე.
 
დაეხმარეთ ჯონს განსაზღვროს, რამდენი განსხვავებული გუნდის შექმნა შეუძლია. რადგან
ეს რიცხვი შეიძლება იყოს ძალიან დიდი, უნდა გამოიტანოთ პასუხის ნაშთი 100 000 000-ზე
მთელი გაყოფისას (modulo 100,000,000).
 
შეტანის ფორმატი:
* სტრიქონი 1: ორი ჰარით გაყოფილი მთელი: N და F.
* სტრიქონები 2..N+1: ხაზი i+1 შეიცავს ერთ მთელს: R_i.

გამოტანის ფორმატი:
* სტრიქონი 1: ერთი მთელი რიცხვი, შესაძლო რაოდენობის ნაშთი 100 000 000-ზე მთელი გაყოფისას.



მაგალითები

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

შენიშვნა

შეტანის დეტალები:
 ჯონს ყავს ოთხი მოთამაშე, რეიტინგებით 1, 2, 8 და 2. ის ქმნის მხოლოდ ისეთ გუნდებს, 
რომლის წევრთა რეიტინგების ჯამიც უნაშთოდ იყოფა 5-ზე.

გამოტანის დეტალები
:
 ჯონს შეუძლია აიყვანოს მოთამაშე 8 რეიტინგით და ერთ-ერთი 2-ინი (8 + 2 = 10),ასევე შეუძლია აიყვანოს
ორივე 2-იანი და კიდევ 1-იანი(2 + 2 + 1 = 5).