In the finale to the Maze Runner saga, Thomas leads his group of escaped Gladers on their final and most dangerous mission yet. To save their friends, they must break into the legendary Last City, a WCKD-controlled labyrinth that may turn out to be the deadliest maze of all. Anyone who makes it out alive will get answers to the questions the Gladers have been asking since they first arrived in the maze.
Given a Maze with NxM blocks each block represent a City.
Thomas who wants to save other Gladers is going on a mission to reach the legendary last city controlled by WCKD. Thomas is initially Standing on the first block of the maze (1,1) (Marked by Red) and is required to reach the final block of maze which is the legendary city represented by the block (x,y)(Marked by Red), Thomas is brave but is weak in Calculations, So he asks you for your help(Yes You!) in Calculation of Number of ways to reach the final block(WCKD-controlled legendary city). Given Thomas can only move Right or Down in the maze.
Thomas is asking your Help! be a Hero Y19!
INPUT:
First line of input contains an integer T i.e the number of queries.
Each of T lines follow space seperated integers N and M i.e., Number of rows in the maze
followed by number of columns.
OUTPUT:
Output N lines Containing the number of ways to reach legendary city.
print answer modulo 10^7+9
CONSTRAINTS:
0<n<=25
0<m<=25
Example for maze of size 3x3 is given below
use long long for C++.
Do not forget to take Modulo