Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P156SUMC - ROUND 6C - Phân đoạn

Xét các đoạn số nguyên [L, R] với các cặp số L, R thỏa mãn (1 <= L <= R <= m)

Đoạn [a, b] nằm trong đoạn [c, d] nếu c <= a <= b <= d.

Nhiệm vụ của bạn là đếm số cách để tạo ra n đoạn [L1, R1], [L2, R2], …, [Ln, Rn] sao cho không có đoạn nào nằm trong đoạn khác, và có ít nhất 1 đoạn có giá trị L[i] = x.

Hai cách được coi là khác nhau nếu tồn tại j (1 <= j <= n) và đoạn thứ j trong hai dãy tương ứng khác nhau.

Input

1 dòng duy nhất chứa 3 số nguyên n, m, x (1 <= n, m <= 10^5 , 1 <= x <= m).

Output

In ra một số nguyên là kết quả của bài toán sau khi lấy dư theo modulo 1 000 000 007.

Example

Test 1:

Input:

3 4 1

Output:

54

 

Test 2:

Input:

1 1 1

Output:

1

 

Test 3:

Input:

2 3 3

Output:

6

Giải thích test 3: Có tất cả 6 cách phân đoạn, đó là:

{[1, 1], [3, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[3, 3], [1, 1]}, {[3, 3], [2, 2]},{[3, 3], [1, 2]}.


Được gửi lên bởi:Admin
Ngày:2015-08-06
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.