考虑 $\text{dp}$。

状态转移方程

我们定义 $f_{i,j}$ 为走到第 $i$ 层，共走了 $j$ 次的方案数，容易得到转移方程：

其中 $down$ 为能走到 $i$ 层的下界，$up$ 为上界。

时间复杂度 $O(n^2k)$，显然无法 $\text{A}$ 掉此题。这时，有经验的 $\text{OIer}$ 就会发现，这是可以用前缀和优化的。我们设 $s_{i,j}=\sum\limits_{k=1}^if_{k,j}$，得到新的转移方程：

时间复杂度 $O(nk)$，可以 $\text{AC}$。

一些细节

显然，由于 $\mid x-y\mid <\mid x-b\mid$ 的限制，你只能在 $b$ 的一侧运动，那么，我们可以将 $b$ 层当做 $0$ 层。

if(a>b) n-=b,a-=b;
else n=b-1,a=b-a;

这样，我们就可以快速的求出 $up$ 和 $down$ 了，$up=n$，$down=\lfloor\frac i 2\rfloor+1$。

初始化：$f_{a,0}=1$

我们注意到，$j$ 次的方案数只依赖于 $j-1$ 次，所以我们可以采用滚动数组对空间进行优化。

代码

#include<cstdio> //for printf,scanf
#include<algorithm> //for min
int const mod=1000000007;
long long n,k,a,b,f[5010],s[5010];
int main(){
	scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
	if(a>b) n-=b,a-=b;
	else n=b-1,a=b-a;
	f[a]=1;
	for(int i=a;i<=n;i++)s[i]=1;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++) f[j]=(s[n]-s[j>>1]-f[j]+mod+mod)%mod;
		for(int j=1;j<=n;j++) s[j]=(s[j-1]+f[j])%mod;
	}
	printf("%lld",s[n]);
	return 0;
}