We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Ones and Twos

Ones and Twos

Problem
Submissions
Leaderboard
Discussions
Editorial

You are using at most A number of 1s and at most B number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * sign are allowed?

Note that, multiplication takes precedence over addition.

For example, if A=2 and B=2, then we have the following expressions:

  • 1, 1*1 = 1
  • 2, 1*2, 1*1*2, 1+1 = 2
  • 1+2, 1+1*2 = 3
  • 2+2, 2*2, 1+1+2, 1*2*2, 1*1*2*2, 1*2+1*2, 1*1*2+2, 1*2+2 = 4
  • 1+2+2, 1+1*2+2 = 5
  • 1+1+2+2, 1+1+2*2 = 6

So there are 6 unique results that can be formed if A = 2 and B = 2.

Input Format

The first line contains the number of test cases T, T testcases follow each in a newline.
Each testcase contains 2 integers A and B separated by a single space.

Constraints

1 <= T <= 105
0<=A<=1000000000
0<=B<=1000

Output Format

Print the number of different evaluations modulo (%) (109+7.)

Sample Input

4
0 0
2 2
0 2
2 0

Sample Output

0
6
2
2

Explanation

  • When A = 0, B = 0, there are no expressions, hence 0.
  • When A = 2, B = 2, as explained in the problem statement above, expressions leads to 6 possible solutions.
  • When A = 0, B = 2, we have 2, 2+2 or 2*2, hence 2.
  • When A = 2, B = 0, we have 1 or 1*1, 1+1 hence 2.

Author

HackerRank

Difficulty

Hard

Max Score

100

Submitted By

647

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature