HackerRank Fundamentals – Matrix Tracing

Challenge: Matrix Tracing

Subdomeniu: Fundamentals (fundamentals)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464726450

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/matrix-tracing/problem

Cerinta

A word from the English dictionary is taken and arranged as a matrix. e.g. "MATHEMATICS"

    MATHE  
    ATHEM  
    THEMA  
    HEMAT  
    EMATI  
    MATIC  
    ATICS  

There are many ways to trace this matrix in a way that helps you construct this word. You start tracing the matrix from the top-left position and at each iteration, you either move RIGHT or DOWN, and ultimately reach the bottom-right of the matrix. It is assured that any such tracing generates the same word. How many such tracings can be possible for a given
word of length m+n-1 written as a matrix of size m * n?

**Input Format**  
The first line of input contains an integer T. T test cases follow.  
Each test case contains 2 space separated integers m & n (in a new line) indicating that the matrix has m rows and each row has n characters.  

**Constraints**  
1 <= T <= 10<sup>3</sup>  
1 ≤ m,n ≤ 10<sup>6</sup>

**Output Format**  
Print the number of ways (S) the word can be traced as explained in the problem statement.
If the number is larger than 10<sup>9</sup>+7,   
print  `S mod (10^9 + 7)` for each testcase (in a new line). 

**Sample Input**

    1
    2 3

**Sample Output**

    3

**Explanation**  
Let's consider a word AWAY written as the matrix

    AWA
    WAY

Here, the word AWAY can be traced in 3 different ways, traversing either RIGHT or DOWN.

    AWA
      Y

    AW
     AY

    A
    WAY

Hence the answer is 3.

**Timelimit**
Time limit for this challenge is given [here](https://www.hackerrank.com/environment)

Cod sursa

#include <bits/stdc++.h>

using namespace std;

const int p=1000000007;
int n, m, t;

long long fmod(long long N) {    if (N<2) return 1; else return (N*fmod(N-1))%p;    }
long long mmi(long long x)  {
    long long result=1, e=p-2;    
    while (e) {
        if (e & 1) result = (result*x)%p;
        x = (x*x)%p;
        e >>= 1;
    }
    return result;
}

int main()
{
    cin >> t;
    while (t--) {
        cin >> n >> m;
        printf("%lld\n", ((fmod(m+n-2)*mmi((fmod(m-1)*fmod(n-1))%p))%p));
    }
    return 0;
}