There are $N$ cities on a circular coastline. The cities are numbered from $1$ to $N$ in clockwise order. For all pairs of cities, there exists a bidirectional road connecting the two cities.

Among all these roads, we call the road connecting two cities $a$ and $b$ the special road. The special road connects two cities, neither of which is city $1$, and is known to be the road with the most beautiful scenery.

Jeongseo plans to travel through the cities following the method below, only by road.

• His travel begins at city $1$. City $1$ is considered to be already visited at the moment he begins his travel.
• During his travel, he should not visit a city that he has already visited, including city $1$, and every city must be visited exactly once.
• None of the roads used in the travel course may intersect with each other.
• The special road must be used exactly once during his travel. It does not matter in which direction he travels through the special road.

Find the number of travel paths that satisfy all of the conditions above.

Input

The first line of input contains a positive integer $N$, denoting the number of cities. ($3 \leq N \leq 1\,000\,000$)

The second line of input contains two space-separated integers $a$ and $b$, denoting the two cities connected by the special road. ($2\leq a, b \leq N$; $a\neq b$)

Output

Print the total number of paths that satisfy the conditions given in the problem statement modulo $1\,000\,000\,007$.

Examples

Input 1

4
2 4

Output 1

2

Input 2

6
5 4

Output 2

11