| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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: | adm |
| 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 PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
