Lucky Arrays

题意翻译

给定一个长度为 $n(1 \le n \le 77777)$ 的数列 $a$ ，初始的时候全为 0。 给出一个 $3 \times 3$ 的矩阵 $w_{i,j}$ ，$w_{i,j} = 1$ 时代表 $(i,j)$ 这个**有序**数对为和谐的数对，否则 $(i,j)$ 不为一个和谐数对。 一个数列 $a$ 是和谐的当且仅当对于所有的 $1\le i \le n-1$ ， $(a_i,a_{i+1})$ 均为和谐数对。 有 $m(1\le m \le 77777)$ 次修改和询问，每次给出两个整数 $v_i,t_i$，将 $a_{v_i} (1 \le v_i \le n)$ 修改为 $t_i(0\le t_i \le 3)$。 每次修改后都询问，如果将数列里所有的 $0$ 都替换为任意 $1$ 到 $3$ 之间的整数（不同位置的 $0$ 可以替换为不同的数），那么最后产生的和谐的数列有多少种。每次修改后的查询并不会使数列发生任何改变。 答案对 $777777777$ 取模。

题目描述

Little Maxim loves interesting problems. He decided to share one such problem with you. Initially there is an array $ a $ , consisting of $ n $ zeroes. The elements of the array are indexed, starting from 1. Then follow queries to change array $ a $ . Each query is characterized by two integers $ v_{i},t_{i} $ . In the answer to the query we should make the $ v_{i} $ -th array element equal $ t_{i} $ $ (a_{vi}=t_{i}; 1<=v_{i}<=n) $ . Maxim thinks that some pairs of integers $ (x,y) $ are good and some are not. Maxim thinks that array $ a $ , consisting of $ n $ integers, is lucky, if for all integer $ i $ , $ (1<=i<=n-1) $ the pair of integers $ (a_{i},a_{i+1}) $ — is good. Note that the order of numbers in the pairs is important, that is, specifically, $ (1,2)≠(2,1) $ . After each query to change array $ a $ Maxim wants to know, how many ways there are to replace all zeroes in array $ a $ with integers from one to three so as to make the resulting array (without zeroes) lucky. Of course, distinct zeroes can be replaced by distinct integers. Maxim told you the sequence of queries and all pairs of integers he considers lucky. Help Maxim, solve this problem for him.

输入输出格式

输入格式

The first line contains integers $ n $ and $ m $ $ (1<=n,m<=77777) $ — the number of elements in the array and the number of commands. The next three lines contain matrix $ w $ , consisting only of zeroes and ones; the $ j $ -th number in the $ i $ -th of these lines — $ w_{i,j} $ . If $ w_{i,j}=1 $ $ (1<=i,j<=3) $ , then pair $ (i,j) $ is good, otherwise it is not good. Matrix does not have to be symmetric relative to the main diagonal. Next $ m $ lines contain pairs of integers $ v_{i},t_{i} $ $ (1<=v_{i}<=n,0<=t_{i}<=3) $ — the queries to change the array.

输出格式

Print $ m $ integers — the $ i $ -th number should equal to the number of ways to replace all zeroes in array $ a $ (changed after the $ i $ -th query) by integers from one to three so as to make the resulting array (without zeroes) lucky. Separate the numbers by whitespaces. As the answers can be rather large, print the remainder from dividing them by $ 777777777 $ .

输入输出样例

输入样例 #1

3 10
1 1 0
1 0 0
1 1 1
1 1
1 3
2 2
3 0
2 1
3 0
3 1
2 0
3 1
1 0

输出样例 #1

3
6
1
1
2
2
1
3
3
6