Parsa is frustrated about being excluded from MAPS events and not winning any cash prizes. To vent his frustration, he challenges you with the following problem:

A k-mino is a connected shape formed by exactly k unit squares (similar to how a domino is a 2-mino).

Parsa gives you a 2 * n grid and asks, in how many distinct ways can you completely cover the 2 * n grid using only k-minos?

Two coverings are considered different if there exists at least one unit square that is part of a different ~k~-mino in the two coverings.

Since the number of valid coverings can be large, print the answer modulo 10^9 + 7.

Input Format:

The first line are integers p and q.

Output:

Output the distance of the fraction p / q from the root of the tree.

Sample Input:

3 5

Sample Output:

3