# Donation - EDITORIAL:

* Author:* kishen1912000

*kishen1912000*

**Editorialist:**# DIFFICULTY:

Easy

# PREREQUISITES:

Dynamic Programming, Combinatorics, Stirling Numbers

# PROBLEM:

Given C identical charities and N unique coins, find the number of ways of distributing the N coins to the C charities such that each charity gets at least 1, 2 or 3 coins based on input. [For a test case, this number (1, 2 or 3) is fixed.]

# EXPLANATION:

Let dp[n][c] denote the number of ways of distributing n coins to c charities. Then, a recursion relation can be derived in each of these cases:

### At least 1 coin each:

dp[n][c] = c*dp[n-1][c] + dp[n-1][c-1]

Where, the first term denotes the number of ways of distributing n-1 coins to c charities and then distribute the n^{th} to any one, which can be done in c ways. The second term denotes the number of ways of distributing n-1 coins to c-1 charities and the n^{th} coin is given to the c^{th} charity.

Similarly, we get the following recurrence relations in the other two cases:

### At least 2 coins each:

dp[n][c] = c*dp[n-1][c] + (n-1)*dp[n-2][c-1]

### At least 3 coins each:

dp[n][c] = c*dp[n-1][c] + \binom{n-1}{2}*dp[n-3][c-1]

The final answer required in each case is dp[N][C]. As the number is huge, use modular arithmetic appropriately where required.

# Time Complexity:

O(T\times N\times C)

# SOLUTIONS:

## Setter's Solution

```
M = 10**9+7
def choose(n,k):
if k==1:
return n
elif k==2:
return (n*(n-1)//2)%M
else:
return 1
for _ in range(int(input())):
n,c,q = [int(s) for s in input().split()]
dp = [[0 for i in range(c+1)] for j in range(n+1)]
for i in range(1,n+1):
dp[i][1] = 0 if i<q else 1
for j in range(2,c+1):
for i in range(j*q,n+1):
dp[i][j] = ((choose(i-1,q-1)*dp[i-q][j-1])%M + (j*dp[i-1][j])%M)%M
print(dp[n][c])
```