Count Good Strings

Count the strings of length 2N consisting only of A and B, with exactly N of each, such that every prefix contains at least as many A as B. Output the count modulo 10000.

输入格式

One line containing a non-negative integer N, 0≤N≤2147483647. The original Constraints section reads o_o and gives no explicit numeric upper bound; following the original Java interface int N, this site covers the entire non-negative int domain without inventing a smaller cap. N=0 is added as a public mathematical boundary: the empty string satisfies the definition. Note that 2N may exceed the range of a 32-bit signed integer.

输出格式

Output an integer in 0..9999, without zero-padding to four digits. For N=0, output 1.

样例 1

输入：

3

输出：

5

样例 2

输入：

0

输出：

1

样例 3

输入：

4

输出：

14

样例说明

Original example N=3 has five strings, AAABBB, AABABB, AABBAB, ABAABB, and ABABAB, so the output is 5. The original explanation said the prefix BA of BABABA has more B, which is wrong; the actual violating prefix is B. The correct original answer is unchanged. The second example, N=0, is the empty-string boundary explicitly added by this site; the third example, N=4, is added by this site, with answer 14.