# Problem Link

Loop Through**Author:**isag2008

# Difficulty

MEDIUM# Prerequisites

Math# Problem Statement

Harrison owns a coin museum. He wants to place all the coins in a matrix representation (size R x C) so that all the coins are visible from the top and side view.He has exactly one coin of all denominations from 1 to (R x C).

For all the coins to be visible, the coin matrix must satisfy the following rule:

For any 2 elements (i_{1}, j_{1}) and (i_{2}, j_{2}) in the matrix X

If i_{1} + j_{1} < i_{2} + j_{2} then

X_{i1, j1} < X_{i2, j2} should hold.

Given R and C, find and print the total number of possible ways of placing the coins; return your answer

in modulo 10^{9}+7.

# Approach

As written in the Problem Statement, we want to find the total number of matrices where:If i

_{1}+ j

_{1}< i

_{2}+ j

_{2}, then X

_{i1,j1}< X

_{i2,j2}

Note that the value of i+j remains same for any specific diagonal of the matrix. Therefore, all the values in the particular diagonal must be greater than all the values in the diagonal above it. The Problem also mentions that each value in the matrix must be unique and lie in the range [1, RxC]. Therefore, the answer for our problem is (d_{1})! x (d_{2})! x (d_{3})! x (d_{R+C-1})! where d_{i} is total number of elements in i^{th} diagonal.

# Solution

```
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pi pair<ll,ll>
#define f first
#define s second
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
ll fact[2000011];
int main(){
int N,M;
cin >> N >> M;
fact[0]=1;
for(ll i=1;i<=N+M;i++){
fact[i]=i*fact[i-1];
fact[i]%=mod;
}
ll ans=1;
int i=N;
int j=1;
for(int d=N-1;d>=1-M;d--){
int cnt=j-(i-d)+1;
ans*=fact[cnt];
ans%=mod;
i--;
j++;
i=max(i,1);
j=min(j,M);
}
cout<<ans;
}
```