27354번 - NoM 서브태스크다국어

문제

Marcel has recently taken up a new hobby: creating zen gardens. He quickly developed his own style, that uses 2ドルN$ 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.

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 2ドルN$ stones exist before he embarks on his journey. Two gardens $A$ and $B$ are considered different if there exists an integer $i,ドル 1ドル ≤ i ≤ 2N,ドル such that:

• the colour of the $i$^th stone in garden $A$ is different from the colour of the $i$^th 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$.

입력

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

출력

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

제한

• 1ドル ≤ M ≤ N ≤ 2,000円$

서브태스크

힌트

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.