Два игрока играют в игру. Изначально на доске записано число $$$n$$$. Игроки ходят по очереди. Если текущее число, записанное на доске, больше $$$0$$$, за свой ход игрок может текущее число поделить на 2 с округлением вниз, либо вычесть 1 из текущего числа, но такой ход можно сделать только тогда, когда текущее число нечетное. (то есть $$$4$$$ за ход можно превратить в $$$2$$$, а $$$7$$$ в $$$3$$$ или в $$$6$$$). Игра продолжается, пока на доске не окажется число $$$0$$$. Игрок, который не может сделать ход, проигрывает(то есть тот игрок, который вынужден ходить тогда, когда на доске записано число $$$0$$$). Определите, кто выигрывает при оптимальной игре обоих игроков - тот, кто ходил первым, или тот, кто ходил вторым. Вам нужно ответить на $$$t$$$ независимых запросов. На каждый из них выведите $$$1$$$, если для данного $$$n$$$ выигрывает первый игрок, и $$$0$$$ иначе. Ответы на запросы выводите в том порядке, в котором они идут во входных данных.

Определим функцию $$$f$$$ от массива целых неотрицательных чисел $$$A$$$ из $$$n$$$ элементов следующим образом: $$$f(A, 0) = $$$ $$$\sum\limits_{i=1}^n a_i$$$;

$$$f(A, i) = $$$$$$\sum\limits_{l=1}^n \sum\limits_{r=l}^n$$$ $$$f(A[l, r], i - 1)$$$, $$$i \gt 0$$$, где $$$A[l, r]$$$ - подмассив массива $$$A$$$ с индексами элементов от $$$l$$$ до $$$r$$$. Вам даны числа $$$n$$$, $$$k$$$ и массив $$$A$$$ из $$$n$$$ элементов. Вычислите $$$f(A, k)$$$ по модулю $$$10^9+7$$$.

У Кроша есть граф, состоящий из $$$n$$$ вершин. Для любой вершины $$$1 \le i \le n - 2$$$ есть ориентированные ребра $$$(i, i + 1)$$$ и $$$(i, i + 2)$$$, для вершины $$$n - 1$$$ есть ориентированное ребро $$$(n - 1, n)$$$. У каждой вершины есть свое значение - $$$a_i$$$. Крош рассматривает пути из вершины $$$1$$$ в вершину $$$n$$$. Стоимость пути определяется как максимум из значений вершин в этом пути. Помогите Крошу посчитать сумму стоимостей по всем возможным путям из вершины $$$1$$$ в вершину $$$n$$$. Выведите ответ по модулю $$$m$$$, где $$$m$$$ - заданное число(необязательно простое).

Крош называет положительное целое число интересным, если оно представляется в виде суммы двух различных степеней двойки, то есть $$$x$$$ $$$-$$$ интересное, если существуют два различных неотрицательных целых числа $$$i \ge 0$$$, $$$j \ge 0$$$, $$$i \neq j$$$, что $$$x = 2^i + 2^j$$$. У Кроша есть большое число $$$m$$$, записанное в двоичной системе счисления. Длина числа не превосходит $$$2*10^5$$$. Помогите Крошу посчитать, сколько есть интересных чисел среди чисел от $$$1$$$ до $$$m$$$.

Вам дано число $$$n$$$. Посчитайте количество способов разложить $$$n$$$ на слагаемые, в котором каждое следующее слагаемое хотя бы в $$$2$$$ раза больше чем предыдущее. Выведите остаток от деления этого количества способов на $$$10^9+7$$$.

Крошу в качестве нового домашнего задания по математике задали посчитать следующую сумму ряда: $$$\sum\limits_{n = 1}^{\infty} \frac{(C_n^k) ^ 2}{2^n}$$$, где $$$k$$$ - заданное число. Помогите ему решить эту задачу, для данного $$$k$$$ выведите сумму ряда. Гарантируется, что ответ - целое число. Выведите его по простому модулю $$$10^9+7$$$.

Вам дано число $$$n$$$. Рассмотрим перестановку $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$. Определим $$$f(l, r) = (((p(l)$$$ $$$mod$$$ $$$p(l + 1))$$$ $$$mod$$$ $$$p(l + 2))$$$ $$$mod$$$ ... $$$mod$$$ $$$p(r))$$$. Красотой перестановки $$$B(p)$$$ назовем сумму $$$f(l, r)$$$ по всем возможным подотрезкам перестановки $$$B(p) = \sum_{l = 1}^n \sum_{r = l}^n f(l, r)$$$. Найдите математическое ожидание красоты случайно выбранной перестановки из $$$n$$$ чисел по заданному простому модулю $$$m$$$. Можно показать, что ответ можно представить в виде несократимой дроби $$$\frac{P}{Q}$$$, где $$$P$$$, $$$Q$$$ – целые числа и для данных ограничений $$$Q \neq 0$$$ $$$(mod$$$ $$$m)$$$.

У Кроша скоро день рождения, и он догадывается, что ему подарят перестановку $$$p$$$ размера $$$n$$$, только не знает, какую именно. В перестановке размера $$$n$$$ все числа различны и каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз. Крошу может не совсем понравиться перестановка, ведь он любит неподвижные точки $$$-$$$ это такие позиции $$$i$$$, в которых $$$p_i = i$$$, и ему хотелось бы, чтобы в перестановке была хотя бы одна неподвижная точка. Поэтому к перестановке, которую ему подарят, он может применять некоторые операции. За одну операцию он может поменять местами любые два соседних элемента в перестановке. Крош научился всегда применять минимальное возможное количество операций, чтобы получить устраивающую его перестановку, но теперь перед ним стоит вопрос $$$-$$$ а какое максимальное количество операций ему придется выполнить в худшем случае?

У Кроша есть три числа $$$a$$$, $$$b$$$, $$$c$$$. Помогите ему посчитать количество массивов длиной $$$n$$$, $$$AND$$$ элементов которых равен $$$a$$$, $$$OR$$$ элементов которых равен $$$b$$$, $$$XOR$$$ элементов которых равен $$$c$$$. Два массива считаются различными, если существует позиция, что в разных массивах на этой позиции стоят разные числа. Так как ответ может получиться большим, выведите его остаток от деления на $$$10^9+7$$$.

Рассмотрим некоторое число без лидирующих нулей(при этом можем рассмотреть 0). Нам нужно сделать так, чтобы оно делилось на три. За один ход мы можем выбрать любую цифру этого числа и, если она не равна 0, то уменьшить ее на один, либо, если она не равна 9, увеличить ее на 1. После этой операции мы должны получить число без лидирующих нулей(однако может получиться 0). Нужно за минимальное количество операций сделать так, чтобы наше число делилось на 3.