各頂点 \(i\) に \(x_i\) が書かれている状態から、\(1\) 回だけ操作した後に頂点 \(i\) に書かれている数の期待値を \(y_i\) とします。

すると、\(xm = y\)、すなわち \(\displaystyle y_i = \sum_{j = 1}^N x_j m_{j, i}\) となるような行列 \(m\) が存在します。
具体的には \(m\) は以下のように構築できます。

• まず \(m\) の全ての要素は \(0\) とする
• 各頂点 \(i\) について考える。頂点 \(i\) の次数を \(d_i\)、隣接する頂点を \(a_{i, 1}, a_{i, 2}, \dots, a_{i, d_i}\) とする
• \(\frac{d_i}{M}\) の確率で頂点 \(i\) に隣接する辺が選ばれ、\(y_i\) への \(x_i\) の寄与割合は \(1\) から \(\frac{1}{2}\) に減るので、\(m_{i, i} = 1 - \frac{d_i}{M} \times \frac{1}{2}\) とする。
  
• また、\(a_{i, j}\) と \(i\) を繋ぐ辺が (\(\frac{1}{M}\) の確率で) 選ばれた場合、\(x_{a_{i, j}}\) が \(\frac{1}{2}\) の割合で \(y_i\) に寄与するので \(m_{a_{i, j}, i}\) を \(\frac{1}{2M}\) とする。
  

\(Am^K\) が問題の答えなので、繰り返し \(2\) 乗法を使って \(m^K\) を求めることで、全体で \(O(N^3 \log(K))\) で解くことができます。