## Count paths

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

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

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.

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

a

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 ?

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

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

@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

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

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!

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

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

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.

this may help you : youtube

@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