Đi thang máy

Trong một tòa nhà có $n$ tầng được đánh số từ $1$ đến $n$. Bạn đang ở tầng $a$ và muốn đi thang máy. Ở tầng $b$ có một phòng thí nghiệm bí mật, nên không bao giờ được dừng ở tầng $b$.

Bạn sẽ thực hiện đúng $k$ chuyến đi liên tiếp. Giả sử bạn đang ở tầng $x$. Bạn chọn tầng đích $y$ thỏa mãn:

• $y\ne x$,
• $|x-y|<|x-b|$ (khoảng cách từ tầng hiện tại tới $y$ nhỏ hơn khoảng cách từ tầng hiện tại tới phòng thí nghiệm).

Thang máy đưa bạn tới tầng $y$ và bạn ghi $y$ vào sổ tay. Tầng tiếp theo lại chọn tương tự xuất phát từ $y$.

Hãy đếm số dãy số phân biệt $y_1,y_2,\dots ,y_k$ có thể được ghi vào sổ tay sau $k$ chuyến đi. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng chứa bốn số nguyên $n$, $a$, $b$, $k$.

Dữ liệu ra

In ra một số nguyên duy nhất — số dãy số phân biệt modulo ${10}^9+7$.

Ràng buộc

• $2\le n\le 5000$
• $1\le k\le 5000$
• $1\le a,b\le n$ và $a\ne b$

Ví dụ