A string is called a Fibonacci string if it satisfies the following constraints:

• Each character of the string is either a 0 or a 1
• There are no two consecutive 1s 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:

1. Let x be the number of 0s in s.
2. Let y be the number of 1s in s.
3. 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