CF479E Riding in a Lift

假设你现在在一栋有 $n$ 层的楼里，可以乘坐电梯在各层之间移动。我们将楼层自下而上编号为 $1$ 到 $n$。你目前在第 $a$ 层。你感到很无聊，于是想乘坐电梯。第 $b$ 层有一间秘密实验室，不允许进入。不过你已经玩嗨了，决定连续坐 $k$ 次电梯。 假设你当前在第 $x$ 层（最初你在第 $a$ 层）。在每一次电梯旅行中，你选择某一不同于 $x$ 的楼层 $y$（即 $y \ne x$），电梯会把你送到那里。因为你不能经过有秘密实验室的 $b$ 层，所以你决定移动距离 $|x-y|$ 必须严格小于当前所在楼层到 $b$ 层的距离 $|x-b|$。即，必须满足 $|x-y| < |x-b|$。每当你成功移动到 $y$ 层时，你会把 $y$ 记到你的笔记本上。 你的任务是，计算经过 $k$ 次电梯旅行后，你可能在笔记本上记录下的不同数字序列个数。由于最终序列数可能非常大，请将其结果对 $1000000007$（$10^9+7$）取模后输出。

输入的第一行为四个用空格分隔的整数 $n$、$a$、$b$、$k$，其中 $2 \leq n \leq 5000$，$1 \leq k \leq 5000$，$1 \leq a, b \leq n$，且 $a \ne b$。

输出一个整数，表示不同数字序列的总个数，对 $1000000007$ 取模。

假设你现在在一栋有 $n$ 层的楼里，可以乘坐电梯在各层之间移动。我们将楼层自下而上编号为 $1$ 到 $n$。你目前在第 $a$ 层。你感到很无聊，于是想乘坐电梯。第 $b$ 层有一间秘密实验室，不允许进入。不过你已经玩嗨了，决定连续坐 $k$ 次电梯。 假设你当前在第 $x$ 层（最初你在第 $a$ 层）。在每一次电梯旅行中，你选择某一不同于 $x$ 的楼层 $y$（即 $y \ne x$），电梯会把你送到那里。因为你不能经过有秘密实验室的 $b$ 层，所以你决定移动距离 $|x-y|$ 必须严格小于当前所在楼层到 $b$ 层的距离 $|x-b|$。即，必须满足 $|x-y| < |x-b|$。每当你成功移动到 $y$ 层时，你会把 $y$ 记到你的笔记本上。 你的任务是，计算经过 $k$ 次电梯旅行后，你可能在笔记本上记录下的不同数字序列个数。由于最终序列数可能非常大，请将其结果对 $1000000007$（$10^9+7$）取模后输出。 由 ChatGPT 5 翻译