8

# Price Pattern

Difficulty: EASY
Contributed By
Vishal Modani
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

#### Ninja observed the prices of a certain stock for some days. He found an interesting pattern in the prices of the stock. Let P(i) be the price of the stock on the ‘ith’ day. He observed that

``````P(i) = P(i-1) + P(i-2) + P(i-1) * P(i-2)
``````

#### Input Format :

``````The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.

The first line of each test case contains three space-separated integers, ‘A’, ‘B’ and ‘N’ Where ‘A’ and ‘B’ denote the prices on the first and second days respectively. ‘N’ denotes the day on which the stock price needs to be calculated.
``````

#### Output Format :

``````For each test case, print a single integer, denoting the price of the stock on the ‘Nth’ day. Since the answer can be very large, calculate the answer modulo 10^9+7.

Output for each test case will be printed in a separate line.
``````

#### Note :

``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````

#### Constraints :

``````1 <= T <= 10
1 <= A,B, <= 10^9
3 <= N <= 5000

Time Limit: 1sec
``````

#### Sample Input 1 :

``````1
1 7 3
``````

#### Sample Output 1 :

``````15
``````

#### Explanation For Sample Input 1 :

``````In the given test case, the price on day 1 is 1, and the price on day 2 is 7. We can calculate the price on day 3 using these two values. Price on day 3 will be 1 + 7 + (1*7) = 15.
``````

#### Sample Input 2 :

``````1
1 3 4
``````

#### Sample Output 2 :

``````31
``````

#### Explanation For Sample Input 2 :

``````In the given test case, the price on day 1 is 1, and the price on day 2 is 3. We can calculate the price on day 3 using these two values. Price on day 3 will be 1 + 3 + (1*3) = 7. Similarly, price on day 4 will be 3 + 7 + (3*7) = 31.
``````
Console