NoM

Marcel has recently taken up a new hobby: creating zen gardens. He quickly developed his own style, that uses $2N$ stones as garden features. Half of the stones are green (they are covered in moss) and are uniquely numbered from $1$ to $N$, while the other half are grey (no moss grows on them) and are likewise uniquely numbered from $1$ to $N$. To create a garden, Marcel will take the stones and place them in some order in a straight line, making sure the distance between any two consecutive stones is precisely $1$ inch.

When it comes to judging the aesthetic appeal of a garden, all gardens are considered beautiful. However, there is one superstition that Marcel has about his gardens: if the distance between two stones that have the same number written on them is equal to a multiple of $M$ inches, then the garden is considered $M-$ unlucky, bringing great misfortune and Code::Blocks crashes upon the one who created that garden. Marcel will never create such a garden. Naturally, all other gardens are considered $M-$ lucky.

Task

As part of his journey to reach enlightenment, Marcel has set out to create all the $M-$ lucky gardens that can be created. However, as he is also a forethoughtful and well organized individual, Marcel would like to know how many $M-$ lucky gardens consisting of $2N$ stones exist before he embarks on his journey. Two gardens $A$ and $B$ are considered different if there exists an integer $i, \ 1 \leq i \leq 2N$, such that:

• the colour of the $i$th stone in garden $A$ is different from the colour of the ith stone in garden $B$, or
• the number written on the $i$th stone in garden $A$ is different from the number written on the $i$th stone in garden $B$.

Input data

The first and only line of the input contains two integers $N$ and $M$, meaning that Marcel will create gardens with $2N$ stones which are $M-$ lucky.

Output data

On a single line, output the number of $M-$ lucky gardens that contain $2N$ stones, modulo $10^9 + 7$.

Restrictions

• $1 \leq M \leq N \leq 2 \ 000$

Example 1

stdin

100 23

stdout

171243255

Example 2

stdin

1 1

stdout

0

Explanation

In the second example, two gardens can be created. However, no garden is $1$-lucky, as for both gardens the distance between the stones numbered with $1$ is $1$ inch, which is a multiple of $M = 1$ inches.