题目描述

有一个竖直立放的三角形木板，上面钉着 $\frac{n(n+1)}{2}$ 颗钉子，以及 $(n+1)$ 个格子（当 $n=5$ 时如图1所示）。每颗钉子与周围钉子的距离均为 $d$，每个格子的宽度也为 $d$。除了最左端和最右端的格子外，每个格子都正对着最下面一排钉子的间隙。

让一个直径略小于 $d$ 的小球从最顶端的钉子正上方自由滚落。小球每碰到一个钉子时，有 $\frac{1}{2}$ 的概率向左或向右落下，且球的中心始终正对着下一颗将要碰上的钉子。图2展示了小球的一条可能路径。

已知在初始状态下（所有钉子都存在），小球落在第 $i$ 个格子中的概率为 $p_i = \frac{C_n^i}{2^n}$，其中 $i$ 为格子编号（从左至右依次为 $0,1,...,n$）。

现在的问题是：在拔掉某些钉子后，计算小球落在编号为 $m$ 的格子中的概率 $p_m$。假设最下面一排钉子不会被拔掉。图3展示了某些钉子被拔掉后小球的一条可能路径。

输入格式

• 第1行：两个整数 $n$（$2 \leq n \leq 50$）和 $m$（$0 \leq m \leq n$）。
• 接下来 $n$ 行：从上至下描述木板上每行的钉子信息。* 表示钉子存在，. 表示钉子被拔掉。空格可能出现在任意位置。

输出格式

• 一行，输出一个既约分数（若概率为 $0$ 则输出 0/1），表示小球落在编号为 $m$ 的格子中的概率 $p_m$。既约分数需满足分子和分母互质。

样例输入

5 2
*
   * .
  * * *
 * . * *
* * * * *

样例输出

7/16

题目来源

NOI 1999