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 <= 10^{5} 

0<=A<=1000000000 

0<=B<=1000  

Output Format

Print the number of different evaluations modulo (%) (10^{9}+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.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
import math

class OneTwo:

	def __init__(self, x):
		self.first = x[0]
		self.second = x[1]
		self.nothing = False if self.first else True

	def pows_second(self, n):
		n = math.floor(math.log(n) / math.log(2))
		return n if n <= self.second else 0

	def end_point(self):
		ad = self.first * 1
		mul = 2 ** self.second
		mul = 0 if mul == 1 else mul
		return ad + mul

	def second_multiply(self, n, available_second):
		second_multiply = n // 2
		return second_multiply if second_multiply <= available_second else available_second

	def first_multiply(self, n):
		return n if n <= self.first else self.first

	def begin_p(self):
		return self.first + 1 if self.first > self.second * 2 else self.second * 2 + 1

	def res_step(self):
		if self.nothing:
			return self.second * 2 / 2
		elif self.first > self.second * 2:
			return self.first
		else:
			return self.second * 2

	def res_count(self):
		end_point = self.end_point()
		result = 0
		begin_p = 1
		result = self.res_step()
		begin_p = self.begin_p()
		n = begin_p
		while n <= end_point:
			powers_second = self.pows_second(n)
			powers_second_result = 2 ** powers_second if powers_second != 0 else 0
			remaining = n - powers_second_result
			available_second = self.second - powers_second
			if remaining > 0:
				remaining -= 2 * self.second_multiply(remaining, available_second)
				remaining -= self.first_multiply(remaining)
			if remaining == 0:
				result += 1
			n += 1
		return int(result)
t = int(input())
a_b = [[int(i) for i in input().strip().split(' ')] for x in range(t)]
for x in a_b:
	inst = OneTwo(x)
	print(inst.res_count())


def solve(a, b):
	results = set()
	for i in range(1, a + 1):
		results.add(i)
	for i in range(1, b + 1):
		results.add(2 ** i)
		results.add(i * 2)
		for k in range(1, a + 1):
			results.add(2 ** i + k)
			results.add(i * 2 + k)
			for m in range(1, b - i + 1):
				results.add(2 ** i + 2 * m + k)
		for m in range(1, b - i + 1):
			results.add(2 ** i + 2 * m)
	print(len(results))
tc = int(input())
for i in range(0, tc):
	(a, b) = map(int, input().split())
	solve(a, b)


import sys
sys.setrecursionlimit(10000)
from collections import Counter
from itertools import cycle, product as prod, permutations as perm, combinations as comb, combinations_with_replacement as combr
from sys import stdin, stdout
read_ints = lambda : list(map(int, input().split()))
read_floats = lambda : list(map(float, input().split()))
MOD = 10 ** 9 + 7

def get_max(level, left):
	ret = 0
	while left and level:
		ret += 2 ** level
		left -= level
		level = min(level - 1, left)
	return ret
memo = {}

def rec(level, left, threshold):
	global memo
	level = min(level, left)
	if level <= 0:
		return 0
	if (level, left) in memo:
		return memo[level, left]
	ret = 0
	diff = 2 ** level - get_max(level - 1, left) - 1
	if diff > threshold:
		ret += (diff - threshold) % MOD
	ret += rec(level - 1, left - level, threshold) + rec(level - 1, left, threshold)
	memo[level, left] = ret
	return ret

def main():
	global memo
	t = read_ints()[0]
	for cas in range(t):
		memo = {}
		(a, b) = read_ints()
		ret = get_max(b, b) + a - rec(b, b, a)
		ret = (ret % MOD + MOD) % MOD
		print(ret)
main()


def fact(a):
	if a == 0:
		return 1
	else:
		return a * fact(a - 1)
t = int(input())
out = []
while t != 0:
	(a, b) = map(int, input().split())
	total = a + b
	if a > 0 and b > 0:
		out.append(fact(total) // (fact(a) * fact(b)))
	elif a == 0 and b > 0:
		out.append(fact(b))
	elif a > 0 and b == 0:
		out.append(fact(a))
	else:
		out.append(0)
	t -= 1
for i in out:
	print(i)


import itertools

def one(n):
	l = []
	for i in range(n + 1):
		l.append(i)
	return l

def two(n):

	def two_sub(num):
		oplist = list(itertools.product('+*', repeat=num))
		l2 = [0]
		for item in oplist:
			str = ''
			for i in range(num):
				str = str + '2'
				str = str + item[i]
			str = str + '2'
			l2.append(eval(str))
			l2 = list(set(l2))
		return l2
	l = []
	for i in range(n):
		temp = two_sub(i)
		for item in temp:
			l.append(item)
		l = list(set(l))
	return l
case_num = int(input())
for i in range(case_num):
	l = list(input().split())
	(num1, num2) = (int(l[0]), int(l[1]))
	if num1 == 0:
		l1 = [0]
	else:
		l1 = one(num1)
	if num2 == 0:
		l2 = [0]
	else:
		l2 = two(num2)
	ret = []
	for i in l1:
		for j in l2:
			ret.append(i + j)
	ret = list(set(ret))
	print(len(ret) - 1)


def rec_two(t, uni_value):
	if t == 1:
		uni_value[2] = 1
		return (uni_value, [2])
	level = [v + 2 for v in rec_two(t - 1, uni_value)[1]] + [max(rec_two(t - 1, uni_value)[1]) * 2]
	for i in level:
		if i not in uni_value.keys():
			uni_value[i] = 1
	return (uni_value, level)

def cal_compose(ar):
	if ar[1] == 0:
		if ar[0] == 0:
			return 0
		else:
			return ar[0]
	else:
		uni_value = {}
		num_two = ar[1]
		uni_value = rec_two(num_two, uni_value)[0]
		if ar[0] == 0:
			return len(uni_value)
		else:
			num_one = ar[0]
			append_value = []
			for plus in range(num_one):
				for i in uni_value.keys():
					if i + plus + 1 not in uni_value.keys():
						append_value.append(i + plus + 1)
					if plus + 1 not in uni_value.keys():
						append_value.append(plus + 1)
			for ap_v in append_value:
				uni_value[ap_v] = 1
			return len(uni_value)
n = int(input().strip())
ar_list = []
for i in range(n):
	temp = [int(a_temp) for a_temp in input().strip().split(' ')]
	ar_list.append(temp)
for i in range(n):
	output = cal_compose(ar_list[i])
	print(output)


T = int(input())

def run(x, y):
	if x * y == 0:
		return max(x, y)
	return (int(x / 2) + y) * 2 + x % 2
for _ in range(T):
	(x, y) = [int(x) for x in input().split()]
	print(run(x, y))


def main(pairs):
	for i in pairs:
		i[0] = int(i[0])
		i[1] = int(i[1])
	for i in pairs:
		s = set()
		a = aset(i[0])
		b = bset(i[1])
		s = s.union(a)
		s = s.union(b)
		for j in a:
			s.add(j)
			for k in b:
				s.add(k)
				s.add(j + k)
		print(len(s) % (10 ** 9 + 7))

def aset(a):
	s = set()
	for i in range(1, a + 1):
		s.add(1 * i)
		s.add(1 ** i)
	return s

def bset(b):
	s = set()
	for i in range(1, b + 1):
		s.add(2 * i)
		s.add(2 ** i)
		if i != b:
			s.add(2 * i + 2 ** (b - i))
	return s
rounds = int(input())
pairs = []
for i in range(rounds):
	(a, b) = input().split()
	pairs.append([a, b])
main(pairs)


import sys

def getSums(a, b, results, offset):
	if a > 0:
		results.update(range(offset + 1, offset + a + 2 * b + 1))
	else:
		results.update(range(offset + 2, offset + 2 * b + 1, 2))
	return results
n = int(input().strip())
for i in range(n):
	results = set()
	(a, b) = [int(tmp) for tmp in input().strip().split(' ')]
	results = getSums(a, b, results, 0)
	for b_i in range(3, b + 1):
		results.add(2 ** b_i)
		results = getSums(a, b - b_i, results, 2 ** b_i)
	print(len(results))


import sys
lines = []
for i in sys.stdin:
	lines.append(i.strip())
test_cases = lines[0]
for line in lines[1:]:
	tmp = line.split(' ')
	a = int(tmp[0])
	b = int(tmp[1])
	if a == 0:
		print(b)
		continue
	elif b == 0:
		print(a)
		continue
	output = []
	if b > 0:
		for i in range(1, b + 1):
			output.append(2 ** i)
		for i in range(2, b):
			for x in range(b - i):
				output.append(2 ** i + 2 * (x + 1))
	output = list(set(output))
	output.sort()
	if a > 0:
		start = 0
		for i in range(a):
			for j in range(start, len(output)):
				output.append(output[j] + 1)
			start = j + 1
		output = list(set(output))
	output.append(1)
	print(len(output))


T = int(input())
for t in range(T):
	(A, B) = map(int, input().split())
	(added, powered, combined, odds) = ([], [], [], [])
	for i in range(B):
		added.append((i + 1) * 2)
	for i in range(B):
		powered.append(2 ** (i + 1))
	for i in range(B - 1):
		combined.append(added[i] + powered[B - i - 2])
	union = list(set(added) | set(powered) | set(combined))
	for i in range(A):
		odds.append(i + 1)
	for i in range(A):
		for j in union:
			odds.append(i + 1 + j)
	union = list(set(union) | set(odds))
	print(len(union))


t = int(input())
for ni in range(t):
	(x, y) = map(int, input().split())
	output = []
	if x > 0:
		start = 0
		output = ['1']
		char = ['+1', '*1', '+2', '*2']
		for i in range(1, x + y):
			for j in range(start, len(output)):
				if output[j].count('1') < x:
					output.append(output[j] + char[0])
					output.append(output[j] + char[1])
				if y > 0:
					if output[j].count('2') < y:
						output.append(output[j] + char[2])
						output.append(output[j] + char[3])
				start = j + 1
	output = list(set(output))
	result = output
	output = []
	if y > 0:
		start = 0
		output = ['2']
		char = ['+2', '*2']
		for i in range(1, x + y):
			for j in range(start, len(output)):
				if output[j].count('2') < y:
					output.append(output[j] + char[0])
					output.append(output[j] + char[1])
				start = j + 1
			output = list(set(output))
	output = list(set(output))
	result = result + output
	result = [eval(i) for i in result]
	result = list(set(result))
	print(len(result))