Little Q likes positive big integers in base k
, but not all big integers. He doesn't like integers with zeroes, including leading zeroes. He is even particular with the occurrence of each digit. Formally it can be described as a matrix g1..k−1,0..n
, for every digit i
from 1
to k−1
, he doesn't like integers having exactly j
-digit i
when gi,j=0
. He also can't accept any digit appearing more than n
times.
Picture from Wikimedia Commons
Little Q's taste changes every day. There are m
days in total, on i
-th day gui,vi
flipped(0
to 1
and 1
to 0
). Let cnt(i)
denotes the number of big integers Little Q likes after i
-th day's change, where cnt(0)
denotes the answer before all changes. Your task is to calculate the following thing :
(∑i=0mcnt(i))mod786433
For each test case, print a single line containing an integer, denoting the answer.
cnt(0)=4 : 112,121,211,2.
cnt(1)=6 : 112,121,211,2,12,21.
cnt(2)=3 : 2,12,21.
