coin-combinations-i

Coin Combinations I

CSES medium

اعتبر نظامًا نقديًا يتكوّن من \(n\) عملات. كل عملة لها قيمة صحيحة موجبة. مهمتك هي حساب عدد الطرق المختلفة التي يمكنك بها تكوين مجموع مالي مقداره \(x\) باستخدام العملات المتاحة.

ترتيب العملات مهم في التركيبة. فعلى سبيل المثال، إذا كانت العملات \({2,3,5}\) والمجموع المطلوب هو \(9\)، فهناك 8 طرق:

2 + 2 + 5
2 + 5 + 2
5 + 2 + 2
3 + 3 + 3
2 + 2 + 2 + 3
2 + 2 + 3 + 2
2 + 3 + 2 + 2
3 + 2 + 2 + 2

الإدخال:

السطر الأول يحتوي عددين صحيحين \(n\) و \(x\): عدد العملات والمجموع المطلوب من المال.
السطر الثاني يحتوي \(n\) عددًا مميزًا \(c_1, c_2, \dots, c_n\): قيمة كل عملة.

المخرجات:

اطبع عددًا صحيحًا واحدًا: عدد الطرق لتكوين المجموع \(x\)، بتطبيق باقي القسمة على \(10^9 + 7\).

القيود:

\(1 \le n \le 100\)
\(1 \le x \le 10^6\)
\(1 \le c_i \le 10^6\)

مثال:

الإدخال:

3 9
2 3 5

المخرجات: