Magic Weed solution codechef

Magic Weed solution codechef

Faizal and Sultan are having a one-on-one 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

  1. First, Sultan kills Faizal. Faizal resurrects, and temporarily loses his ability to resurrect.
  2. Then, Faizal kills Sultan. Sultan resurrects, and Faizal’s resurrection is now active.
  3. Faizal kills Sultan again. Sultan resurrects.
  4. Sultan kills Faizal, who resurrects. Now Sultan has no more chances to revive.
  5. 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 space-separated 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.


Magic Weed solution codechef

  • 1T20001≤T≤2000
  • 0N1050≤N≤105
  • 0M1050≤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 

2 1
12 6
6969 8563

Sample Output 1

Magic Weed solution codechef



Test Case 1: The death sequences corresponding to the 77 possible fights are:

Leave a Comment