NoM

Time limit: 0.25s Memory limit: 512MB Input: Output:

Marcel has recently taken up a new hobby: creating zen gardens. He quickly developed his own style, that uses 2N2N stones as garden features. Half of the stones are green (they are covered in moss) and are uniquely numbered from 11 to NN, while the other half are grey (no moss grows on them) and are likewise uniquely numbered from 11 to NN. 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 11 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 MM inches, then the garden is considered MM- 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 MM- lucky.

Task

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

  • the colour of the iith stone in garden AA is different from the colour of the ith stone in garden BB, or
  • the number written on the iith stone in garden AA is different from the number written on the iith stone in garden BB.

Input data

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

Output data

On a single line, output the number of MM- lucky gardens that contain 2N2N stones, modulo 109+710^9 + 7.

Restrictions

  • 1MN2 0001 \leq M \leq N \leq 2 \ 000
# Points Restrictions
1 9 1N,M51 \leq N, M \leq 5
2 12 1N,M1001 \leq N, M \leq 100
3 13 1N,M3001 \leq N, M \leq 300
4 18 1N,M9001 \leq N, M \leq 900
5 48 No further restrictions.

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 11-lucky, as for both gardens the distance between the stones numbered with 11 is 11 inch, which is a multiple of M=1M = 1 inches.

Log in or sign up to be able to send submissions!