Count paths

Submit solution
Points: 15
Time limit: 1.0s
Memory limit: 256M
Author:
moncef
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
    _mehdi_bachiri_  commented on Aug. 3, 2023, 1:48 a.m.

    Hello, why do I have TLE on the last case I used DP iteratively with bottom-up please tell me why it doesn't work


    • 0
      AkramElOmrani  commented on Aug. 4, 2023, 2:09 a.m.

      it's because you are recomputing the dp every time. just compute it for let's say ans(\(n = 1000, m = 1000\)) and answer in \(\mathcal{O(1))}\) the queries.


      • 0
        _mehdi_bachiri_  commented on Aug. 5, 2023, 12:55 a.m.

        Oh thanks, I always forget this thing, I encountered the same problem in fibonacci queries problem, but I forgot LOL. Thanks!


  • 0
    AkramElOmrani  commented on Sept. 18, 2021, 12:08 a.m. ← edited

    a


  • 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 ??


    • 0
      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


    • 3
      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
        mouad_smi  commented on Sept. 15, 2021, 6:30 p.m. ← edited

        I've tried DP with bottom up manner and it gives me TLE in the last test case; and i also tried combinatorics but i think i did stg bad with the MOD; if someone can take a look at my code it's in this link " never mind i've found the solution " , i will delete it when i find the solution or someone helps me. Thank you!


        • 0
          AkramElOmrani  commented on Sept. 16, 2021, 11:51 p.m.

          next time share your code via ideone it's better. I myself got stuck with this problems, the idea is that you should do some memoization instead of computing the answer over and over again


          • 0
            mouad_smi  commented on Sept. 17, 2021, 10:01 p.m.

            yep man i totally forgot about memoization, it worked thank you.


          • 0
            mouad_smi  commented on Sept. 17, 2021, 12:07 a.m.

            Nice thank you, but if you know how to do it with combinatorics can you please tell me how do we deal with the MOD cause i know the formula but still i don't know how to do it.


    • 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