Трансформация массива положительных целых чисел \(a_1,a_2,\dots,a_n\) определена как замена \(a\) на массив \(b_1,b_2,\dots,b_n\), получающийся операцией \(b_i=a_i\oplus a_{(i\bmod n)+1}\), где \(\oplus\) обозначает операцию побитового XOR (исключающего ИЛИ).
Вам даны целые числа \(n\), \(t\) и \(w\). Мы считаем, что массив \(c_1,c_2,\dots,c_n\) (\(0 \le c_i \le 2^w-1\)) является бугабу тогда и только тогда, когда существует массив \(a_1,a_2,\dots,a_n\) такой, что после трансформации массива \(a\) ровно \(t\) раз массив \(a\) превращается в \(c\).
Например, если \(n=6\), \(t=2\), \(w=2\), то массив \([3,2,1,0,2,2]\) — бугабу, потому что его можно получить, трансформировав массив \([2,3,1,1,0,1]\) \(2\) раза: \(\) [2,3,1,1,0,1]\to [2\oplus 3,3\oplus 1,1\oplus 1,1\oplus 0,0\oplus 1,1\oplus 2]=[1,2,0,1,1,3]; \\ [1,2,0,1,1,3]\to [1\oplus 2,2\oplus 0,0\oplus 1,1\oplus 1,1\oplus 3,3\oplus 1]=[3,2,1,0,2,2]. \(\)
Массив \([4,4,4,4,0,0]\) не бугабу, потому что \(4 > 2^2 - 1\). Массив \([2,3,3,3,3,3]\) не бугабу, потому что он не может быть получен трансформацией одного массива \(2\) раза.
Вам дан массив \(c\), значения на некоторых позициях которого неизвестны (вначале только \(m\) элементов известны, остальные — нет). Также есть \(q\) модификаций, где каждая модификация меняет какой-либо элемент \(c\). Модификация может изменить, известен ли элемент на какой-либо позиции или нет, а так же, возможно, переопределить элемент на позиции, которая уже известна.
Вам нужно посчитать, сколько возможных массивов \(c\) (с произвольными элементами на неизвестных позициях) являются бугабу после каждой модификации. Выведите \(i\)-й ответ по модулю \(p_i\) (\(p_i\) — заданный массив из \(q\) элементов).
Примечание
В первом примере \(n=3\), \(t=1\) и \(w=1\). Пусть \(?\) обозначает неизвестную позицию в массиве \(c\).
В первом запросе \(c=[1,0,1]\). Единственный возможный массив \([1,0,1]\) — бугабу, потому что он может быть получен одной трансформацией из \([0,1,1]\). Поэтому ответ \(1\bmod 123\,456\,789 = 1\).
Во втором запросе \(c=[1,1,1]\). Единственный возможный массив \([1,1,1]\) — не бугабу. Поэтому ответ \(0\bmod 111\,111\,111 = 0\).
В третьем запросе \(c=[?,1,1]\). Есть два возможных массива: \([1,1,1]\) и \([0,1,1]\). Из них только \([0,1,1]\) является бугабу, потому что может быть получен одной трансформацией из \([1,1,0]\). Поэтому ответ \(1\bmod 987\,654\,321=1\).
В четвертом запросе \(c=[?,1,?]\). Есть четыре возможных массива, из них \([0,1,1]\) и \([1,1,0]\) являются бугабу. \([1,1,0]\) может быть получен из \([1,0,1]\) одной трансформацией. Поэтому ответ \(2\bmod 555\,555\,555=2\).