QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
统计

Bobo 有一个 $n + m$ 个节点的有向图,节点用 $1, 2, \dots, (n + m)$ 编号。他还有一个 $n$ 行 $(n + m)$ 列的矩阵 $P$.

  • 如果在 $t$ 时刻他位于节点 $u$ ($1 \leq u \leq n$),那么在 $(t + 1)$ 时刻他在节点 $v$ 的概率是 $P_{u, v} / 10000$.
  • 如果在 $t$ 时刻他位于节点 $u$ ($u > n$),那么在 $(t + 1)$ 时刻他在节点 $u$ 的概率是 $1$.

$0$ 时刻 Bobo 位于节点 $1$,求无穷久后,他位于节点 $(n + 1), \dots, (n + m)$ 的概率 $p_1, p_2, \dots, p_m$。

输入格式

输入文件包含多组数据,请处理到文件结束。

每组数据的第一行包含两个整数 $n$ 和 $m$.

接下来 $n$ 行,其中第 $i$ 行包含 $n + m$ 个整数 $P_{i, 1}, P_{i, 2}, \dots, P_{i, n + m}$.

  • $n, m \geq 1$
  • $n + m \leq 500$
  • $1 \leq P_{i, j} \leq 10000$
  • $P_{i, 1} + P_{i, 2} + \dots + P_{i, n + m} = 10000$
  • 至多 $100$ 组数据,除了 $1$ 组外都满足 $n + m \leq 50$.

输出格式

对于每组数据,输出 $m$ 个整数表示 $p_1, p_2, \dots, p_m$. 格式如下:如果 $p_i = \frac{P}{Q}$(其中 $\mathrm{gcd}(P, Q) = 1$),则输出 $P \cdot Q^{-1} \bmod (10^9+7)$.

样例输入

1 2
5000 2000 3000
2 1
1000 2000 7000
1000 2000 7000
2 2
1000 2000 3000 4000
1000 2000 3000 4000

样例输出

800000006 200000002
1
428571432 571428576

样例解释

对于第一组数据,$p_1 = \frac{2}{5}, p_2 = \frac{3}{5}$.