# [SOLUTION] Come Back Home solution codechef 2021 – Spider AlgoCup Codechef

## Come Back Home solution codechef 2021

There are KK villages numbered from 11 to KK in the countryside. You live in a village numbered 11. All villages are interconnected.

The cost of traveling from one village to another is 11 coin. You have exactly NN coins with you. Your task is to find in how many ways you can spend exactly NN coins so that you start from your home village 11 and return to your home village in the end.

As the answer can be large, print it modulo 109+7109+7.

### Input: Come Back Home solution codechef 2021

• First line will contain TT, number of testcases. Then the testcases follow.
• Each testcase contains a single line of input, two integers N,KN,K.

### Output: Come Back Home solution codechef 2021

For each testcase, output in a single line answer modulo 1000000007.

### Constraints Come Back Home solution codechef 2021

• 1T10001≤T≤1000
• 1N1091≤N≤109
• 2K1092≤K≤109

### Sample Input: Come Back Home solution codechef 2021

3
3 4
4 3
5 2


### Sample Output:

6
6
0


### EXPLANATION:

First Test case has 4 villages and 3 coins. Possible six ways are – 1->2->3->1, 1->2->4->1, 1->3->2->1, 1->3->4->1, 1->4->2->1, 1->4->3->1

Second test case has 3 villages and 4 coins. Possible six ways are – 1->2->1->2->1, 1->3->1->3->1, 1->2->1->3->1, 1->3->1->2->1, 1->2->3->2->1, 1->3->2->3->1

Third test case has 2 villages and 5 coins. There is no possible way you can reach to your home village in exactly 5 coins.