问题描述
在一个$N$个点(标号$1$~$n$),$M$条边的有向图上,一开始我在点$u$,每一步我会在当前点的出边中等概率的选一条走过去,求走了恰好$K$步后走到每个点的概率.
输入描述
第一行两个正整数$N,M$,表示点数和边数.
接下来$M$行,每行两个正整数$X,Y$.表示一条$X$向$Y$的一条有向边(保证没有重边和自环).
接下来一个正整数$Q$,表示询问个数.
接下来$Q$行,每行两个正整数$u,K$,表示开始的点和步数.
$N \leq 50, M \leq 1000, Q \leq 20, u \leq n, K \leq 10^{9}$.
每个点保证至少有一个出边.
输出描述
$Q$行,每行$N$个数字,用空格隔开,第$i$个数字表示从$u$开始走$K$步到$i$的概率.
考虑到输出的答案可能会有精度问题,经过一定的分析后可以发现答案一定可以被表示成$\frac{X}{Y}$的形式,你只需输出$X \times Y^{10^9+5} \ mod \ (10^9+7)$的值即可.
在每行后面多输出一个空格,否则可能会使你PE.
输入样例
3 2
1 2
1 3
1
1 1
输出样例
0 500000004 500000004
Hint
这是一个三个点,两条边的有向图,它们分别是$(1->2,1->3)$.现在在1号点,走了一步后,有1/2的概率走到了2,有1/2的概率走到了3,本来应该输出 0 0.5 0.5
而根据上面所说的,应输出$1*2^{10^9+5} \ mod \ (10^9+7)=500000004$.
