Arov was given a problem to solve, by his brother Dharma.
The problem was like, given integers, N and K, Arov has to find the number (possibilities) of non-increasing arrays of length K, where each element of the array is between 1 and N (both inclusive).
He was confused, regarding this problem. So, help him solve the problem, so that, he can give the answer of the problem, to his brother Dharma.
Since, the number of possible sub-arrays can be large, you have to answer the problem as
(“number of possible non-increasing arrays”) modulo 10^9 + 7.
Explanation:
Assume N=2 and K=5 as input.
In such case the Possible Arrays are as follows:
{1, 1, 1, 1, 1}
{2, 1, 1, 1, 1}
{2, 2, 1, 1, 1}
{2, 2, 2, 1, 1}
{2, 2, 2, 2, 1}
{2, 2, 2, 2, 2}
Hence, the answer is 6 (6 % (10^9 + 7)).
Input:
Two space-separated integers, N and K.
Output:
Output in a single line, the number of possible non-increasing arrays, modulo 10^9 + 7.#include <stdio.h>
#define m 1000000007
int main()
{
static int n,k,count;
scanf("%d %d",&n,&k);
int arr[n];
int i,j;
for(i=0;i<n;i++)
arr[i]=i+1;
for(i=2;i<=k;i++)
{
count=0;
for(j=0;j<n;j++)
{
count=(count+arr[j])%m;
arr[j]=count;
}
}
printf("%d",arr[n-1]);
return 0;
}
INPUT_1:
17 8
OUTPUT:
735471
INPUT_2:
10 3
OUTPUT:
220
INPUT_3:
2 5
OUTPUT:
6
INPUT_4:
16 7
OUTPUT:
170544
ILLUSTRATION
