QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[0]

# 605. Alternating permutation

Statistics

In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set {1,2,3,,n} is a permutation (arrangement) of those numbers so that each entry is alternately greater or less than the preceding entry.

Calculate the number of the alternating permutations p1,p2,,pn such that p1=a and pn=b.

Input

The first line of the input contains three integers n, a and b.

It is guaranteed that 2n2000 and 1a,bn and ab.

Output

Output a single line contains a single integer, indicating the answer.

Example

Input

2000 249 662

Output

979748465