В Томской области очень любят волшебные формулы. Вот, например, несколько таких формул.

Пусть задана последовательность целых положительных чисел p₁, p₂, ..., p_n. Тогда выпишем волшебные формулы:

Здесь «mod» обозначает операцию взятия остатка от деления.

Выражение означает применение побитовой операции xor (исключающее «ИЛИ») к целым числам x и y. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как «^», в Pascal — как «xor».

Волшебные формулы в Томской области очень любят, а вот считать их — не очень. Поэтому ваша задача по заданной последовательности p посчитать значение Q.