A Study in Pink
All submissions for this problem are available.
Sherlock Holmes is chasing a cab driver and he(Holmes) is carrying a gun with which he can shoot the . cabbie. Both Sherlock Holmes and the cab driver are initially in the first cell (1,1) and the Jail is at (N,M). Sherlock Holmes will shoot the cab exactly one time whenever they both are in same cell i.e. whenever they are in the same cell, the strength of the car reduces by 1. The cabdriver’s car has strength equal to K i.e. after exactly K shots car will break down. So in order to save the pain of taking the cab driver to the police, he decided to break down his car at (N,M) i.e. he will take his last shot at (N,M).
The size of the grid is N x M and none of them can go out of the grid. Also both the cab driver and Sherlock can either go to the left or down (i.e if one is at (x,y) then he can either go to (x+1,y) or to (x,y+1) ). Both Sherlock Holmes and the cab driver are travelling at the same speed.
Given the size of the grid and the strength of the car, you need to tell the no. of ways Sherlock could have stopped the cabbie.
Note: They are always together in the first and last cell. Two ways are different if path taken by at least one of them different in both ways.
First line of input contains T, the no. of testcases.
Each test case contains one line containing 3 integers N M and K separated by a space.
Output of each test case is a single integer denoting the no. ways. Since this number can be very large, output the number after taking mod with 1,000,000,007 (10^9 +7)
Input: 5 2 1 2 2 2 1 2 2 2 2 2 3 3 3 3 Output: 1 0 2 2 12
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions