PROBLEM LINK:
Author: Lalit Kundu
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran
DIFFICULTY:
EASY – MEDIUM
PREREQUISITES:
Combinatorics
PROBLEM:
Given three positive integers N, L and R, find the number of nondecreasing sequences of size at least 1 and at most N, such that each element of the sequence lies between L and R, both inclusive.
QUICK EXPLANATION:
Number of nondecreasing sequences of size exactly K will be Choose(K + R  L, K). Where Choose(N, R) is number of ways to choose R elements from N distinct elements.
Summation of Choose(K + R  L, K) for all K between 1 and N (inclusive) will be Choose(N + R  L + 1, N)  1.
In the question it is given that the answer should be printed mod (10^6+3) which is a prime number.
Choose(N, R) mod P for N > P can be found by using Lucas Theorem.
EXPLANATION:
Let us assume that our nondecreasing sequence is of length K, i.e in other terms the sequence a[1], a[2], a[3] …… a[K] and a[i] <= a[i+1] and L <= a[i] <= R for each i.
Let us replace each a[i] of the sequence with a[i] – L. Let P = R – L. Now each a[i] satisfies the condition 0 <= a[i] <= P.
Subtask 1:
We can solve this by using DP. Make a dp[][] array where dp*[j] stores number of nondecreasing sequences ending with j and are of length i.
If a[i] = j, and a[i  1] = k, then k should be <= j. So dp[i][j] will be sum of dp[i – 1][k] such that k <= j.
Boundary case : dp[1][j] = 1 for all j.
Calculate these values for all 1 <= i <= MAX_N and 0 <= j <= MAX_P. For each test case output the sum of dp[i][P] for all i.
Complexity = O(N * P) Where P = R  L.
Subtasks 2 & 3:
Now let us consider that there are K red balls lying in a row. Now for each i, add a[i+1] – a[i] blue balls between i’th red ball and i+1’th red ball in the row. Add a[1] blue balls before 1st red ball and P – a[K] blue balls after K’th red ball in the row.
Few observations:

We can see that there will be exactly P blue balls in the row.
Proof: Total number of blue balls = a[1] + a[2] – a[1] + a[3] – a[2] + ……a[K] – a[K – 1] + P – a[K]. All the terms of sequence a[] will be cancelled out leaving us with P. 
Two different sequences produce different permutations of red and blue balls.
Proof: Let us assume the two sequences are a[1], a[2]…a[K] and b[1], b[2]…b[K]. Let i be the smallest index where a[i] != b[i]. Simply assume a[0] = 0 and b[0] = 0. So there will be a[i]  a[i  1] blue balls between i’th and i1’th red balls in the first permutation and b[i] – b[i1] blue balls between i’th and i1’th red balls in the second permutation. Hence, the two permutations are different. 
For each permutation of red and blue balls there exists a sequence which produces it.
Proof: The sequence can be generated this way, each a[i] will be equal to (total number of blue balls to the left of it). In this sequence a[i] will never be greater than a[i+1] because there any blue ball to the towards left of i’th red ball in the row will also be to the left of i+1’th red ball in the row. So the sequence is nondecreasing. As the total number of blue balls is P, the highest element of the sequence can be P. Hence all the elements lie in the range 0 to P. 
Observations 2 and 3 are enough to say that the mapping between the sequences and the permutation of balls is a Bijection. You can read about Bijective functions here.
So total number of sequences will be equal to total number of permutations. The total number of permutations of K red balls and P blue balls in a row is a standard result which is equal to Choose(K + P, K).
This much solution is enough to solve the second subtask. Iterate through each of K between 1 and N and add Choose(K + P, K) to the answer.
Actually we can reduce this summation to single term to solve subtask 3. The summation is Choose(P + 1, 1) + Choose(P + 2, 2) ….+ Choose(P + N, N). Add and subtract Choose(P + 1, 0) to the summation, which shouldn’t change the value of the sum.
Choose(P+1, 1) + Choose(P+1, 0) = Choose(P + 2, 1) (Since it is known that Choose(N, R) + Choose(N, R – 1) = Choose(N + 1, R)).
Now Choose(P + 2, 2) + Choose(P + 2, 1) = Choose(P + 3, 2).
Now Choose(P + 3, 3) + Choose(P + 3, 2) = Choose(P + 4, 3).
… So on till N’th term gives Choose(P + N + 1, N).
So the final answer is Choose(P + N + 1, N) – 1.
You can find the best ways to calculate Choose(N, R) mod P here.