- Time limit: 1.00 s
- Memory limit: 512 MB
A string is called a Fibonacci string if it satisfies the following constraints:
- Each character of the string is either a
0
or a1
- There are no two consecutive
1
s in the string
You are given a positive int n. In this problem we will consider Fibonacci strings of length n. You are also given two nonnegative ints a and b. These are used to define the weight of a string. The weight w(s) of a Fibonacci string is calculated as follows:
- Let x be the number of 0s in s.
- Let y be the number of 1s in s.
- The weight of s is x^a \cdot y^b
Note that z^0 is 1 for any z. In particular, when calculating the weight of a string assume that 0^0 = 1.
Given n, a and b find the sum of weights of all Fibonacci strings of length n. Return that sum modulo 10^9+7
Input
Integers n, a and b.
Output
The sum of weights of all Fibonacci strings of length n. Return that sum modulo 10^9+7
Constraints
- 1 \le n \le 10^9
- 0 \le a \le 25
- 0 \le b \le 25
Examples
Input:
3 0 0
Output:
5
Input:
3 0 1
Output:
5
Input:
10 10 10
Output:
518500021
Input:
5000 20 20
Output:
880245669