You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

随机游走模型（Random Walk Model）是一种随机过程（stochastic process），用来描述一个变量随时间的变化路径，其中每一步的变化是由随机误差或概率转移决定的，并且这些变化相互独立、同分布。它常用于刻画股票价格、汇率等金融时间序列的不可预测性。

在本题中，我们有 $n$ 个不同的事件（状态），编号为 $1, 2, \dots, n$ 。

在任意两个事件 $i, j$ 之间，有一个转移概率 $P(i, j)$，表示当当前事件是 $i$ 时，下一事件是 $j$ 的概率。所有转移概率构成一个 概率转移矩阵 $P$，满足每行之和等于 $1$，且 $P(i,j) \ge 0$。

小明刚刚处理完事件 $s$，他将连续处理 $k$ 个事件。在整个处理过程中，不能出现事件 $x$（即处理序列中不允许包含 $x$ 事件）,最终回到起点$s$的概率是多少。

请你计算：发生这个复杂事件的概率是多少？

输入格式

• 第一行：一个整数 $n$ — 事件的个数（$1 \le n \le 50$）

• 第二行：三个整数 $s, x, k$

  • $s$ — 起始事件编号（$1 \le s \le n$）
  • $x$ — 不允许处理的事件（$1 \le x \le n ,x \neq s$）
  • $k$ — 处理的事件个数

  注意：这里的“处理的事件个数 $k$”指从初始状态开始，依次经历 $k$ 次状态变化后结束的路径长度。

• 接下来 $n$ 行，每行 $n$ 个实数，第 $i$ 行第 $j$ 列为 $P(i,j)$，即从事件 $i$ 转移到事件 $j$ 的概率。 每行的概率和为 $1$，每个概率满足 $0 \le P(i,j) \le 1$。

数据保证

$40\%$的数据满足:$k \leq 7$

$100\%$的数据满足:$k \leq 200$

输出格式

• 输出一个实数，表示所求概率。
• 答案保留6位小数

样例输入

3
1 2 2
0.5 0.5 0
0.2 0.3 0.5
0.4 0.5 0.1

样例输出

0.250000

说明

样例中：

• 事件总数为 $n = 3$
• 起点 $s = 1$
• 不允许出现的事件 $x = 2$
• 处理 $2$ 个事件（即转移 $2$ 步）

路径要求：

1. 从事件 $1$ 出发。
2. 转移两次后回到事件 $1$。
3. 中间和终点事件中都不允许出现事件 $2$。