CF256E Lucky Arrays

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

The first line contains integers $ n $ and $ m $ $ (1

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 $ .