Этим летом Джек ездил в летнюю школу в России. Там он завел много новых друзей, а также встретил красивую девушку. По возвращении домой родители подарили Джеку новый ноутбук, и теперь он всегда может быть на связи со своими новыми друзьями. Естественно, получив подарок, Джек сразу стал переписываться со своей подругой Ирой.

Отправив несколько сообщений, Джек заметил, что ноутбук, а точнее его клавиатура, работает не так, как он ожидал. В процессе ввода сообщения у ноутбука иногда внезапно срабатывает клавиша «Home», в результате чего курсор ввода перемещается в начало строки. Так, например, если у Джека в процессе ввода строки «irailikeyou» клавиша «Home» сработала после ввода букв «a» и «y», то получится строка «ouilikeyira».

Джек планировал набрать строку \(s\), нажимая по очереди на соответствующие клавиши. Закончив набор, он посмотрел на экран и увидел строку \(t\). Теперь он хочет понять, может ли она быть результатом его ввода, если единственная неисправность его ноутбука — лишние срабатывания клавиши «Home», либо у его ноутбука есть еще проблемы. Помогите Джеку.

У Тани было \(n\) мячей, она пронумеровала их от \(1\) до \(n\). Но, к сожалению, Таня уронила все мячи в реку и сильно расстроилась.

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

Исключающее или двух чисел обозначается как \(\oplus\) и соответствует операции «xor» в паскале или «^» в других языках. Чтобы вычислить x \(\oplus\) y для двух целых чисел, необходимо сделать следующее: представить каждое из чисел в двоичной системе счисления и сделать \(i\)-й разряд результата единицей, если он равен единице ровно в одном из чисел \(x\) и \(y\). Например, \(3 \oplus 2 = 11_2 \oplus 10_2 = 1_2 = 1, 17 \oplus 5 = 10001_2 \oplus 101_2 = 10100_2 = 20\).

Помогите Тане! Посчитайте сумму по всем парам ее мячей исключающих или их номеров. Таня не любит большие числа, так что ответ необходимо вывести по модулю \(10^9 + 7\). Например, если у Тани было 3 мяча, то искомое значение равно \((1 \oplus 2) + (1 \oplus 3) + (2 \oplus 3) = 3 + 2 + 1 = 6\).

Вася часто ходит в гости к Пете. Для того, чтобы попасть к Пете во двор, надо ввести код, состоящий из четырех цифр. Обычно друзья ходили вместе, но в этот раз Вася пришел один, а Петя ждет его у себя.

Вася не помнит код, но у него есть несколько вариантов. Кроме того, Васе почему-то запомнился факт, что квадрат числа, составленного из первых двух цифр кода, в сумме с квадратом числа, состоящего из последних двух цифр кода, имеет при делении на семь остаток один. То есть, если код представляет собой «ABCD», где «A», «B», «C», «D» — некоторые цифры, тогда \(AB^2 \ + \ CD^2\) имеет остаток 1 при делении на 7. Например, код 2843, является одним из возможных кодов, поскольку \(28^2 \ + \ 43^2 \ = \ 2633 \ = \ 376 \ · \ 7 \ + \ 1\), а 8243 — нет, поскольку \(82^2 \ + \ 43^2 \ = \ 8573 \ = \ 1224 \ · \ 7 \ + \ 5.

У Васи есть несколько вариантов того, каким может быть код. Помогите ему определить, какие из вариантов могут быть кодом от входа в Петин двор.

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске \(8 \times 8\) ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из \(n\) столбцов, \(i\)-й из которых содержит \(a_i\) клеток. Нижние клетки всех столбцов образуют один горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку, соответственно.

Помогите Васе расставить на его доске минимальное число ладей требуемым образом

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из \(n\) городов его королевства. Петир выяснил, что в \(i\)-м городе ищут работу \(a_i\) воинов, которых он может завербовать в свою армию.

Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из \(i\)-го города, необходимо заплатить ему \(c_i\) золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для \(i\)-го и \(j\)-го города выполнено \(a_i < a_j\), то \(c_i \le c_j\).

Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.

Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.