Contents
Magic Weed solution codechef

For Solution
Click Here!
Faizal and Sultan are having a oneonone faceoff. Before stepping into the fight, each of them smoked a special kind of weed from Jhalwa. Smoking kk grams of this weed grants the smoker the ability to resurrect kk times after dying. Sultan smoked MM grams of this weed, and Faizal smoked NN grams.
Magic Weed solution codechef
However, Faizal was addicted to this kind of weed since his childhood, and so developed a side effect: if Faizal dies and is resurrected, he temporarily loses his ability to resurrect; and only gains it back after killing Sultan at least once (given that he hasn’t resurrected NN times already). Sultan has no such restriction.
The fight ends whenever one of the two is killed without being able to resurrect. In other words, either Sultan is killed M+1M+1 times, or Faizal is killed N+1N+1 times, or Faizal is killed twice in a row.
Any possible fight can be described by the sequence of deaths – for example, with N=2N=2 and M=2M=2, the string FSSFSFSSFS encodes the fight where:
Magic Weed solution codechef
 First, Sultan kills Faizal. Faizal resurrects, and temporarily loses his ability to resurrect.
 Then, Faizal kills Sultan. Sultan resurrects, and Faizal’s resurrection is now active.
 Faizal kills Sultan again. Sultan resurrects.
 Sultan kills Faizal, who resurrects. Now Sultan has no more chances to revive.
 Faizal kills Sultan, who stays dead; and the fight ends.
Faizal’s wife Mohsina is getting anxious about the fight and asks for your help in finding the number of different ways the fight between Faizal and Sultan can end up happening. Because this value can be quite large, compute it modulo 109+7109+7.
Two fights are considered different if and only if the sequence of deaths corresponding to those fights are different. For example, the sequence SFSF is different from the sequence FSFS and hence these represent different fights.
Input Format
Magic Weed solution codechef
 The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
 Each test case consists of a single line of input, containing two spaceseparated integers NN and MM.
Output Format
For each test case, output a single line containing the answer – the possible number of fights between Faizal and Sultan, modulo 109+7109+7.
Constraints
Magic Weed solution codechef
 1≤T≤20001≤T≤2000
 0≤N≤1050≤N≤105
 0≤M≤1050≤M≤105
 Sum of NN over all test cases will not exceed 106106
 Sum of MM over all test cases will not exceed 106106
Sample Input 1
3
2 1
12 6
6969 8563
Sample Output 1
Magic Weed solution codechef
7
255
988402422
Explanation
Test Case 1: The death sequences corresponding to the 77 possible fights are:
 SS
 SFS
 FSS
 FSFS
 FF
 SFF
 FSFF

For Solution
Click Here!