> [!NOTE] Problem
> **Input**: The first input line has two integers $n$ and $x$: the number of coins and the desired sum of money. The second line has $n$ distinct integers $c_{1},c_{2},\dots,c_{n}$: the value of each coin.
>
>**Output**: Print one integer: the number of distinct ways you can produce a money sum $x$ modulo $10^{9}+7.$
>
>**Constraints:**
>- $1 \leq n\leq 100$
>- $1 \leq x \leq 10^{6}$
>- $1 \leq c_{i} \leq 10^{6}$
Solution. Let $T(k)$ denote the number of ways to construct $x$ using $c_{1},\dots c_{n}.$ Then $T(k) = T(k-c_{1})+\dots+T(k-c_{n})$with $T(0)=1$ and for $k<0,$ $T(k)=0.$ Topological order $k=1,\dots,x.$
```run-python
max_x = 10**6
md = 10**9+7
# n, x = list(map(int, input().split()))
# c = list(map(int, input().split()))
n, x = 3, 9
c = [2,3,5]
dp = [0]*(max_x+1); dp[0]=1
for k in range(1,x+1):
for i in range(n):
if(k-c[i]>=0): dp[k] = (dp[k] + dp[k-c[i]]) % md
print(dp[x])
```
# Applications
The [[Dice Combinations]] problem is a special case of this where $c_{i}=i$ for $i=1,\dots,6.$