CF256E Lucky Arrays

Little Maxim 非常喜欢有趣的问题。他决定和你分享这样一道题。 最开始有一个长度为 $n$ 的数组 $a$，所有元素都为 0。数组的下标从 1 开始。接下来有若干次修改操作，每次操作用两个整数 $v_i, t_i$ 描述。对于每次操作，你需要将数组中第 $v_i$ 个元素赋值为 $t_i$，即 $a_{v_i} = t_i$，其中 $1 \leq v_i \leq n$。 Maxim 认为某些整数对 $(x, y)$ 是“好”的，某些则不是。他认为：如果一个长度为 $n$ 的整数数组 $a$，对于所有 $i$（$1 \leq i \leq n-1$），都满足 $(a_i, a_{i+1})$ 是“好”的整数对，则称数组 $a$ 是“幸运的”。需要注意，数对的顺序很重要，例如 $(1,2) \ne (2,1)$。 每次修改操作后，Maxim 都想知道：有多少种方案，可以将数组 $a$ 中所有的 0 都替换成 1 到 3 之间的整数（每个 0 可以替换成不同的数），使得最终得到的数组（不含 0 时）是“幸运的”。 Maxim 会把所有的修改操作和他认为“好的”整数对都告诉你。请你帮他解决这个问题。

第一行为两个整数 $n$ 和 $m$，表示数组的长度和操作次数，$1 \leq n, m \leq 77777$。 接下来的三行表示矩阵 $w$，每行有三个只包含 0 和 1 的整数，第 $i$ 行第 $j$ 个数为 $w_{i,j}$。若 $w_{i,j} = 1\, (1\leq i, j \leq 3)$，则数字对 $(i, j)$ 是“好”的，否则不是。矩阵不一定关于主对角线对称。 接下来 $m$ 行，每行包含一组整数 $v_i, t_i\, (1\leq v_i \leq n, 0\leq t_i\leq 3)$，表示一次修改操作。

输出 $m$ 个整数，第 $i$ 个整数表示经过第 $i$ 次修改后，将所有的 0 替换成 $1$ 至 $3$ 之间的整数，使得最终数组为“幸运的”不同方案数。用空格分隔。由于答案可能很大，请对 $777777777$ 取模后输出。

由 ChatGPT 5 翻译