Мирко большой любитель шахмат и программирования, но обычные шахматы уже наскучили ему, поэтому он начал экспериментировать и придумал свою игру. Он взял шахматную доску с N рядами и N столбцами и расположил на ней K ладей. Игра Мирко следует таким правилам: 1. У каждой ладьи есть своя сила, заданная натуральным числом. 2. Ладья видит все клетки поля в своем ряду и своем столбце кроме той, на которой стоит сама. 3. Клетка считается атакованной в том случае, если побитовый XOR сил всех ладей, которые видят эту клетку, положителен. Изначально Мирко некоторым образом расположил ладьи на поле, и теперь собирается сделать P перемещений. Каждый раз он будет брать одну ладью и ставить ее на другую клетку поля (при этом ладья не обязательно будет перемещена вдоль ряда или столбца в котором она стоит). После каждого перемещения, определите сколько клеток на поле атакованы.

Юная Мирка - начинающий музыкант. Она играет на мульти-пианино. Мульти-пианино имеет бесконечно много мульти-клавиш, обозначенных целыми числами, которые можно воспринимать как ноты. Мульти-композиция (композиция для мульти-пианино) может быть представлено как последовательность чисел, обозначающих мульти-клавиши, которые должны быть нажаты (то есть ноты, которые должны быть сыграны).

Мирка услышала на мульти-радио мульти-композицию, и теперь она хочет сыграть ее. К сожалению, она не не умеет точно узнавать ноты по звуку, но может понимать, была ли нота с радио выше или ниже последней сыгранной ей ноты. Поэтому, она решила сыграть мульти-композицию следующим образом:

1. Перед началом игры, она выберет целое неотрицательное число K .

2. В начале, она сыграет правильную ноту (ее мульти-учитель сказал ей, какую клавишу нужно нажать первой)

3. Когда она услышит ноту выше, чем она только что сыграла, она будет нажимать на мульти-клавишу с числом на K больше, чем она только что сыграла.

4. Когда она услышит ноту ниже, чем она только что сыграла, она будет нажимать на мульти-клавишу с числом на K меньше, чем она только что сыграла.

5. Когда она услышит такую же ноту, как только что сыграла, она будет нажимать на ту же мульти-клавишу, что только что сыграла.

Помогите Мирке выбрать такое K , чтобы она правильно сыграла как можно больше нот мульти-композиции.

Мирко и Славко играют в игру. Мирко ходит первым и выбирает непустое множество пар чисел от 1 до N (включительно). При этом числа в одной паре должны быть различны и взаимнопросты. Например, для N = 5 , Мирко может выбрать такое множество пар: {(1, 2), (3, 4), (2, 5), (3, 5)}.

Славко ходит вторым и его задача - найти разделяющий элемент для множества пар Мирко. Разделяющим элементом для множества пар называется такое число x из диапазона [2: N ] , что для каждой пары ( a , b ) из множества выполняется одно из двух условий:

1. a , b < x

2. a , b ≥ x

Например, множество пар {(1, 2), (3, 4)} имеет разделяющий элемент x = 3 .

Если разделяющий элемент существует, Славко обязательно его найдет, и тогда он выиграет. Мирко же выиграет, если Славко не сможет найти разделяющий элемент. Он просит вас помочь: определите, как много множеств пар, удовлетворяющих условию, он может выбрать, чтобы гарантированно выиграть. Так как это число может быть очень большим, выведите его по модулю 1 000 000 000.