思路

所有路径总价值对权值数组是线性的。设格子 $i$ 在全部长度为 $k$ 的路径中一共被经过 $w_i$ 次，则当前答案就是 $\sum a_iw_i$。修改一个位置时，只需按照权值差更新这一项。

令 $f_{t,i}$ 表示从任意格子出发，移动恰好 $t$ 步后到达格子 $i$ 的路径数。初始有 $f_{0,i}=1$，转移来自相邻格子。

做法

先用动态规划求出所有 $f_{t,i}$。考虑一条路径在第 $t$ 步位于 $i$：它的前缀有 $f_{t,i}$ 种。由于格子链是无向图，从 $i$ 再走 $k-t$ 步的方案数同样等于 $f_{k-t,i}$。因此

预处理全部 $w_i$ 后，计算初始加权和。每次把 $a_p$ 改成 $x$ 时，将答案增加 $(x-a_p)w_p$，再保存新权值。所有运算都对 $10^9+7$ 取模。

正确性证明

固定格子 $i$ 和路径中的时刻 $t$。任意一条在第 $t$ 步经过 $i$ 的路径，可以唯一拆成一个终点为 $i$、长度为 $t$ 的前缀和一个起点为 $i$、长度为 $k-t$ 的后缀。二者方案数分别为 $f_{t,i}$ 与 $f_{k-t,i}$，乘积就是该时刻经过 $i$ 的路径数。

对所有时刻求和得到 $w_i$，恰好统计了格子 $i$ 在所有路径价值中的总出现次数。再对所有格子按权值加权，即得到全部路径价值之和。单点修改只改变对应格子的加权项，因此增量更新始终保持正确答案。

复杂度

预处理时间复杂度为 $O(nk)$，每次修改为 $O(1)$，总时间复杂度为 $O(nk+q)$；空间复杂度为 $O(nk)$。