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.|

P172SUMA - ROUND 2A - Time Travel

Bằng các nghiên cứu mang tính đột phá về du hành thời gian của mình, giáo sư Livw đã phát minh ra một hệ thống đặc biệt giúp con người có thể du hành tới các khoảng thời gian nhất định. Có n sự kiện được thiết lập trong hệ thống, được đánh số từ đến theo trình tự thời gian. Khoảng cách giữa 2 sự kiện liên tiếp ii + 1 (1 ≤ i < n) là 1 đơn vị thời gian. Hệ thống cho phép con người du hành từ sự kiện x đến y với x ≠ y.

Việc du hành đến một sự kiện bất kỳ có thể làm thay đổi một hoặc một số sự kiện khác. Điều này có thể gây nên những hậu quả nghiêm trọng. Giáo sư Livw đã tiến hành nghiên cứu và tìm ra một tính chất giúp đảm bảo sự an toàn cho việc du hành thời gian. Ông tìm ra được một sự kiện b trong số n sự kiện, mà với một sự kiện x bất kỳ, việc du hành đến một sự kiện y sẽ không ảnh hưởng, hoặc ảnh hưởng không đáng kể tới các sự kiện khác nếu |x - y| < |x - b|.Ông áp dụng điều kiện trên với mọi chuyến du hành trong hệ thống.

Ban đầu, giáo sư đang ở thực tại - sự kiện thứ a trong n sự kiện, và muốn thực hiện một hành trình gồm k chuyến du hành thời gian. Một hành trình X với k chuyến du hành có thể coi như một dãy gồm các sự kiện X1, X2,..., Xk (1 ≤ Xi ≤ n), hành trình sẽ bắt đầu từ a đến X1, sau đó từ X1 đến X2,…, và cuối cùng đến Xk. Trước khi thực hiện kế hoach, giáo sư muốn tính toán tổng số lượng các hành trình khác nhau mà ông có thể thực hiện được. 2 hành trình độ dài kX Y khác nhau nếu tồn tại 1 chỉ số i (1 ≤ i ≤ k) mà Xi ≠ Yi. Do bận việc chuẩn bị nên giáo sư muốn nhờ sự trợ giúp của các bạn.

Input

1 dòng gồm 4 số nguyên n, k, a, b (2 ≤ n ≤ 5000, 1 ≤ a, b ≤ n, a ≠ b, 1 ≤ k ≤ 5000).

Output

In ra một số nguyên là kết quả của bài toán. Kết quả là số dư của phép chia số lượng các hành trình khác nhau cho 1000000009 (1e9 + 9).

Example

Test 1:
Input:
6 1 3 5
Output:
2
Test 2:
Input:
6 2 3 5
Output:
3

Giải thích: Ở test đầu tiên, từ 3 có thể đến được 2 và 4.


Được gửi lên bởi:adm
Ngày:2017-07-21
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 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

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