I. Mostly Successful Mailman
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A farmer is trying to line up his cows, numbered $$$1$$$ through $$$N$$$, from lightest to heaviest. The numbers of the cows represent their weight. However, the weight of the cows is not immediately apparent at inspection, so the farmer makes a few mistakes. If the farmer makes more than $$$K$$$ mistakes, then he'll be fired. Find the number of ways the farmer can order the cows modulo $$$1009$$$.

Clarification added after the contest:

The farmer lines up his cows in some order $$$a_1, a_2, ..., a_N$$$. The number of mistakes are the number of $$$i$$$ such that $$$a_i \neq i$$$, for $$$1 \leq i \leq N$$$. If the farmer makes exactly $$$K$$$ mistakes, he will still be fired.

Find the number of ways the farmer can order the cows without getting fired modulo $$$1009$$$.

Input

Line $$$1$$$: Two space separated integers $$$K$$$ ($$$1 \le K \le 10$$$) and $$$N$$$ ($$$1 \le N \le 100$$$).

Clarification added after the contest: N is the first integer in the line, and K is the second.

Output

Line $$$1$$$: The number of ways for the farmer to line up the cows, modulo $$$1009$$$.

Example
Input
10 3
Output
46