## Problem

### Statement

In Republic of AtCoder, Snuke Chameleons (Family: Chamaeleonidae, Genus: Bartaberia) are very popular pets. Ringo keeps Snuke Chameleons in a cage.
A Snuke Chameleon that has not eaten anything is blue. It changes its color according to the following rules:

• A Snuke Chameleon that is blue will change its color to red when the number of red balls it has eaten becomes strictly larger than the number of blue balls it has eaten.
• A Snuke Chameleon that is red will change its color to blue when the number of blue balls it has eaten becomes strictly larger than the number of red balls it has eaten.

Initially, every Snuke Chameleon had not eaten anything. Ringo fed them by repeating the following process K times:

• Grab either a red ball or a blue ball.
• Throw that ball into the cage. Then, one of the chameleons eats it.

After Ringo threw in balls, all the chameleons were red. We are interested in the possible ways Ringo could have thrown in balls. How many such ways are there? Find the count modulo . Here, two ways to throw in balls are considered different when there exists such that the color of the ball that are thrown in the throw is different.

### Constraints

and are integers.

### Input

Input is given from Standard Input in the following format:

### Output

Print the possible ways Ringo could have thrown in balls, modulo .

### Sample

Input #1

Output #1

Explanation #1
We will use R to represent a red ball, and B to represent a blue ball. There are seven ways to throw in balls that satisfy the condition: BRRR, RBRB, RBRR, RRBB, RRBR, RRRB and RRRR.
Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

Input #5

Output #5

## Solution

• 红球个数严格大于蓝球
• 红球和蓝球个数相等，且最后一个球是蓝色的

1. 显然无论如何都不会使所有变色龙都变成红色，方案数为

2. 符合条件的序列必定满足：

• 最后一个球为蓝球
• 存在个不相交的子序列

我们将其放入平面直角坐标系中，以红色球为，蓝色球为，那么最后一定要走到，然后再取一个蓝球，走到。满足第二个条件则需要使得不存在路径上的点满足。这是因为不满足条件的情况一定是先取了很多蓝球，使得后面的蓝球不够匹配。由于最多有个蓝球能不和红球匹配，这时蓝球个数和红球个数之差一定大于，即一定有某个点满足

3. :
符合条件的序列必定满足：

• 存在个不相交的子序列

与前面的情况相同，类似地，序列个数等价于从走到且不经过的点的路径条数。