No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Sereja and Intervals

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSereja is interested in intervals of numbers, so he has prepared a problem about intervals for you. An interval of numbers is a pair of integers [*l*, *r*] (1 ≤ *l* ≤ *r* ≤ *m*). Interval [*l*_{1}, *r*_{1}] belongs to interval [*l*_{2}, *r*_{2}] if the following condition is met: *l*_{2} ≤ *l*_{1} ≤ *r*_{1} ≤ *r*_{2}.

Sereja wants to write out a sequence of *n* intervals [*l*_{1}, *r*_{1}], [*l*_{2}, *r*_{2}], ..., [*l*_{n}, *r*_{n}] on a piece of paper. At that, no interval in the sequence can belong to some other interval of the sequence. Also, Sereja loves number *x* very much and he wants some (at least one) interval in the sequence to have *l*_{i} = *x*. Sereja wonders, how many distinct ways to write such intervals are there?

Help Sereja and find the required number of ways modulo 1000000007 (10^{9} + 7).

Two ways are considered distinct if there is such *j* (1 ≤ *j* ≤ *n*), that the *j*-th intervals in two corresponding sequences are not equal.

Input

The first line contains integers *n*, *m*, *x* (1 ≤ *n*·*m* ≤ 100000, 1 ≤ *x* ≤ *m*) — the number of segments in the sequence, the constraints on the numbers in segments and Sereja's favourite number.

Output

In a single line print the answer modulo 1000000007 (10^{9} + 7).

Examples

Input

1 1 1

Output

1

Input

3 5 1

Output

240

Input

2 3 3

Output

6

Note

In third example next sequences will be correct: {[1, 1], [3, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[3, 3], [1, 1]}, {[3, 3], [2, 2]}, {[3, 3], [1, 2]}.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2022 16:56:58 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|