Mảng may mắn

Cho mảng $a$ gồm $n$ phần tử, ban đầu tất cả đều bằng $0$. Chỉ số bắt đầu từ $1$.

Cho ma trận $w$ kích thước $3\times 3$, các phần tử chỉ là $0$ hoặc $1$. Cặp có thứ tự $(x,y)$ với $1\le x,y\le 3$ được gọi là tốt nếu $w_{x,y}=1$. Lưu ý ma trận không cần đối xứng, và cặp có thứ tự nên $(1,2)$ khác $(2,1)$.

Mảng $a$ (sau khi đã thay thế) được gọi là may mắn nếu với mọi $1\le i\le n-1$, cặp $(a_i,a_{i+1})$ là tốt.

Có $m$ truy vấn, mỗi truy vấn là hai số nguyên $v_i,t_i$: gán $a_{v_i}:=t_i$ (với $0\le t_i\le 3$; giá trị $t_i=0$ có nghĩa vị trí $v_i$ trở lại giá trị $0$).

Sau mỗi truy vấn, hãy đếm số cách thay thế tất cả các vị trí đang mang giá trị $0$ trong mảng $a$ bằng số nguyên trong $\{1,2,3\}$ sao cho mảng thu được là may mắn. Các vị trí $0$ khác nhau có thể được thay bằng số khác nhau. Vì đáp án có thể lớn, in ra phần dư khi chia cho $777777777$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Ba dòng tiếp theo mô tả ma trận $w$: dòng thứ $i$ chứa ba số $w_{i,1},w_{i,2},w_{i,3}$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $v_i,t_i$.

Dữ liệu ra

In ra $m$ số nguyên, mỗi số trên một dòng: đáp án sau truy vấn thứ $i$.

Ràng buộc

• $1\le n,m\le 77777$
• $w_{i,j}\in \{0,1\}$
• $1\le v_i\le n$
• $0\le t_i\le 3$

Ví dụ