Count paths


Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

You are given a grid of size \(N \times M\). You are at cell (1,1) and you want to go to the cell (N,M). In each step from each cell you can either move right or down. How many different paths exist ?

Two paths are different if at a given step the two paths lead to different cells.

Input Specification

The first line of the input contains one integer \(T\) the number of test cases (\( 1 \leq T \leq 1000\)).

Each test case consists of a line with two integers \(N\) and \(M\) (\( 1 \leq N,M \leq 1000\)).

Output Specification

For each test case output one line containing the number of different paths to go from the top left to bottom right.

As this number can be very big, print it modulo \(1000000007\).

Sample Input

3
2 3
1 5
3 3

Sample Output

3
1
6

Comments


  • 0
    AkramElOmrani  commented on Jan. 16, 2021, 9:28 p.m. edited

    J'ai utiliser la DP j'ai fait gaffe au modulo je crois que ma solution est très rapide pourriez vous me dire pourquoi j'ai un TLE dans le troisième teste ?


  • 0
    AkramElOmrani  commented on Jan. 16, 2021, 8:55 p.m.

    Yeah I did It but apparently the second case doesnt work don't know why could you tell me the prob in my code


  • 0
    saadyo  commented on May 26, 2020, 2:16 a.m.

    je sais pas est ce que c'est a cause de python (moins rapide que les autres langages)j'arrive pas a valide le dernier test sachant que j'ai optimiser ma solution est ce qu'il y a quelqun qui l'a resolu avec python ??


    • 1
      Yassineosip  commented on May 27, 2020, 4:40 p.m.

      @saadyo the same things happening with me in the problem "Azuz's Anagram" i saw that u solved it with python3 how ? the case 7 for me doesnt work


    • 2
      aymanrs  commented on May 26, 2020, 6:04 p.m. edit 2

      tu as essaye d'utiliser la combinatoire ? je l'ai fait (en C++) et c'est tres tres rapide dons j'imagine que ca va marcher en python. aussi si tu es decide a utilise la DP, essaye une "bottom-up manner" ca consiste a calculer les sous-problemes d'abord et puis deduire les resultats sans passer par la recursion


    • 0
      Yassineosip  commented on May 26, 2020, 4:02 a.m.

      @saadyo the same things happening with me in the problem "Azuz's Anagram" i saw that u solved it with python3 how ? the case 7 for me doesnt work