Tangalar bilan yigʻish usullari

Shart

Birinchi qatorda tanga turlari soni n, ikkinchi qatorda n ta turli nominal, uchinchi qatorda summa S berilgan. S summani tangalar bilan yigʻishning necha usuli borligini chiqaring; har bir nominaldan istalgancha olish mumkin, tartib ahamiyatsiz (1+2 va 2+1 — bitta usul). Javobni 10^9 + 7 ga boʻlgandagi qoldiq sifatida chiqaring.

Misollar

3
1 2 5
5

4

1
2
3

0

Cheklovlar

• 1 ≤ n ≤ 50
• 1 ≤ nominal ≤ 1000
• 0 ≤ S ≤ 10^4