P17357 [ECNA 2024] Brownian Bears

Ursula Major 博士是享誉国际的熊类研究专家，尤其擅长研究棕熊——在北美许多地区也称灰熊。她最著名的成就是发现了一种极其罕见的棕熊亚种：“布朗运动熊”（Brownian bear）。这种熊的觅食行为似乎由规律性与随机性的一种奇妙混合所支配。 目前，Major 博士正在研究一对生活在东西走向狭长地带上的布朗运动熊。这片领地上有 $n$ 个等间距地点可供熊采摘浆果，Major 博士从西向东将它们编号为 $1,2,\ldots,n$。 每天早晨，每只熊都会在 $n$ 个地点之一醒来，并随机选择向东或向西移动到相邻地点。令人惊讶的是，它向任一方向移动的概率都恰好是 $50\%$。Major 博士目前的理论是，这源自熊大脑中的某种量子力学现象。 如果一只熊早晨位于端点地点 $1$ 或 $n$，它会以相等概率选择移动到唯一的相邻地点，或者留在原地。作出选择后，熊会在选中的地点觅食一整天，并在那里过夜。第二天早晨，这一过程重新开始。 Major 博士特别关注两只熊共同觅食——即位于同一地点——的日子，因此计划观察它们一段时间，最长可能达到一个月，或者持续到经费用尽。第一个观察日开始时，两只熊在不同地点醒来。请计算在整个实验期间，它们至少有一天会共同觅食的概率。 注意，两只熊可以擦肩而过而不共同觅食。例如，某天开始时两只熊分别位于地点 $4$ 和 $5$；若前者向东、后者向西移动，它们只是在早晨相互经过，之后不会在同一地点觅食。

输入一行，包含四个整数 $n,x,y,d$。其中 $2\le n\le 100$ 表示地点数量；$1\le x,y\le n$ 且 $x\ne y$，表示第一个观察日开始时两只熊所在地点；$1\le d\le 31$ 表示观察天数。

输出两只熊在 $d$ 个观察日中至少有一天共同觅食的概率。将概率表示为最简分数 $a/b$，其中 $a$ 为非负整数，$b$ 为正整数。格式参见样例。