**Prerequisites :** DP , Maths

**Difficulty :** Medium

**Expected Complexity :** O(N*M + T).

**Editorial :**

The very first thing to observe is that since each of the apple received is distinct , one of the ways is surely going to be of the form : a1 < a2 < a3 < … < an , where ai denotes apples received by ith shinigami. If we find the number of ways to arrange this , we can multiply this by N! to find all possible distinct ways. So our problem reduces to finding the number of ways to distribute M apples such that **a1 + a2 + a3 + … + an = M and 0 < a1 < a2 < … < an.**

Let’s rewrite each ai as ai = a(i-1) + 1 + yi , where yi >= 0.

a1 = 1 + y1;

a2 = a1 + 1 + y2;

a3 = a2 + 1 + y3;

…

an = a(n-1) + 1 + yn;

Replacing all a(i-1) in ai , we get :

a1 = 1 + y1;

a2 = 2 + y1 + y2;

a3 = 3 + y1 + y2 + y3;

…

an = n + y1 + y2 + … + yn;

**summation of all ai = 1 + 2 + 3 + … + n + n*y1 + (n-1) * y2 + (n-2) * y3 + … yn;**

renaming our yi as y(n-i+1) , we can get :

sum = n*(n+1)/2 + summation i*yi;

M - n*(n+1)/2 = summation i*yi;

now if lhs < 0 , then answer is 0.

otherwise K = summation i*yi , where yi >= 0;

we can easily solve this using the recurrence : **solve(i,K) = solve(i-1,K) + solve(i,K-i).**

In short, the answer is : * N! * solve(n , m - n(n+1)/2).**