 0

# Recursive Multiply

Difficulty: MEDIUM Contributed By
Vishal Modani
Avg. time to solve
20 min
Success Rate
80%

Problem Statement

#### You are given two positive integers. Your task is to multiply the two numbers using recursion by performing a minimum number of operations. Note that you can use addition, subtraction, and/ or bit shifting, but you cannot use the multiplication or division operation.

##### Input Format :
``````The very first line of input contains an integer ‘T’ denoting the number of test cases.

The first and the only line of every test case contains two space-separated positive integers ‘M’ and ‘N’.
``````
##### Output Format :
``````For each test case, print the result obtained after multiplying these two numbers.
``````
##### Note :
``````The result can be very large. So, print the answer modulo 1000000007.

You do not need to print anything, it has already been taken care of. Just return the result.
``````
##### Constraints :
``````1 <= T <= 10
1 <= M, N <= 10^8

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````2
5 10
3 9
``````
##### Sample Output 1 :
``````50
27
``````
##### Explanation of sample input 1 :
``````For the first test case we have, M = 5 and N = 10. Therefore our result is M*N = 5*10 = 50.

For the second test case we have, we have M = 3 and N = 9. Therefore our result is M*N = 3*9 = 27.
``````
##### Sample Input 2 :
``````3
1 5
3 4
1 1
``````
##### Sample Output 2 :
``````5
12
1
``````   Console