题目描述

$n$ 层楼，开始在 $a$ 层。可以上下楼，设开始在 $x$ 层，走到了 $y$ 层，则这次上下楼必须满足 $|x-y|<|x-b|$，并且不能到达 $b$ 层。

求上下楼 $k$ 次的不同走法数量，对 $10^9+7$ 取模。

输入格式

一行四个整数 $n,a,b,k$，$2\le n\le 5000$，$1\le k\le 5000$，$1\le a,b\le n$，$a\ne b$。

输出格式

输出一个整数表示答案，对 $10^9+7$ 取模。

5 2 4 1

2

5 2 4 2

2

5 3 4 1

0