Counting Langford Sequences

Time limit2sMemory limit512 MB

Summary

Count Langford sequences of length 2n where the numbers at positions x and y are equal, for n up to 12.

Level: Medium4 of 10
Topics: Backtracking, Recursion, Brute force, Implementation
Solved: No attempts yet

Problem

A Langford sequence is a sequence of length 2n that satisfies the following conditions.

It contains two copies of each natural number from 1 to n.
There is exactly 1 number between the two 1s.
There is exactly 2 numbers between the two 2s.
...
There are exactly n numbers between the two n's.

For example, 3, 1, 2, 1, 3, 2 is a Langford sequence for n=3.

Given n, count the number of Langford sequences of length 2n. That alone is not interesting, so we add one more condition: the x-th number and the y-th number are equal. (Positions are numbered starting from 1.)

Input

Three natural numbers n, x, y are given. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n)

Output

Print the number of Langford sequences of length 2n in which the x-th number and the y-th number are equal.

Examples3

Example 1
Input
```
3 1 5
```
Expected output
```
1
```
Example 2
Input
```
7 4 10
```
Expected output
```
4
```
Example 3
Input
```
12 1 3
```
Expected output
```
19776
```