E. DZY любит мосты
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

DZY владеет 2m островами рядом с домом, острова пронумерованы от 1 до 2m. DZY очень любит мосты, поэтому между некоторыми островами он построил мосты. Проход по одному такому мосту занимает у DZY один день.

DZY любит математику, поэтому все мосты он строил по следующему правилу. Для каждой пары островов u, v (u ≠ v) он построил 2k различных мостов, соединяющих эти острова, где (a|b значит, что b делится на a). Все эти мосты были двусторонние.

DZY также построил некоторые мосты для связи его дома с островами. В частности, с островом i его дом соединен ai различными мостами. Эти мосты односторонние, поэтому после того, как DZY пройдет по одному из них, дороги домой уже не будет.

DZY решил погулять по островам. В самом начале прогулки он находится дома. Затем DZY выбирает один из мостов, идущих от его дома. Так он добирается до некоторого острова. После этого он проводит на островах t дней. Каждый день он выбирает, остаться ли ему на текущем острове и отдохнуть, или же дойти по мосту до другого острова. На острове можно оставаться дольше, чем на день. Также разрешается пересекать любой мост более одного раза.

Предположим, что в момент времени сразу после t-го дня DZY находится на i-м острове. Обозначим за ans[i] количество способов дойти до i-го острова ровно за t дней прогулки по островам. Ваша задача — подсчитать ans[i] для каждого i по модулю 1051131.

Входные данные

Чтобы избежать громоздких входных данных, массив a генерируется следующим образом. Вам даны s первых элементов массива: a1, a2, ..., as. Все остальные элементы надо подсчитать по формуле: ai = (101·ai - s + 10007) mod 1051131 (s < i ≤ 2m).

В первой строке записаны три целых числа: m, t, s (1 ≤ m ≤ 25; 1 ≤ t ≤ 1018; 1 ≤ s ≤ min(2m, 105)).

Во второй строке записано s целых чисел: a1, a2, ..., as (1 ≤ ai ≤ 106).

Выходные данные

Чтобы избежать громоздких выходных данных, выведите только xor-сумму всех ans[i] по модулю 1051131 (1 ≤ i ≤ 2m). Другими словами выведите (ans[1] mod 1051131) xor (ans[2] mod 1051131) xor... xor (ans[nmod 1051131).

Примеры
Входные данные
2 1 4
1 1 1 2
Выходные данные
1
Входные данные
3 5 6
389094 705719 547193 653800 947499 17024
Выходные данные
556970
Примечание

В первом примере массив ans равен [6, 7, 6, 6].

В первом примере, если юноша хочет быть на острове 1 через, гуляя по островам 1 день, то у него есть 6 различных способов сделать это:

  1. дом —> 1 -(остаемся на острове)-> 1
  2. дом —> 2 —> 1
  3. дом —> 3 —> 1
  4. дом —> 3 —> 1 (обратите внимание, что между островами 1 и 3 есть два различных моста)
  5. дом —> 4 —> 1
  6. дом —> 4 —> 1 (обратите внимание, что между домом и островом 4 есть два различных моста)

Во втором примере (a1, a2, a3, a4, a5, a6, a7, a8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849). Массив ans равен [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335].