дп

Ёлочная гирлянда состоит из n лампочек, пронумерованных от 1 до n. Каждая лампочка либо горит (обозначим «1»), либо не горит («0»). Текущее состояние гирлянды задано строкой a.

Монтажник Егор хочет, чтобы гирлянда выглядела по-праздничному — в виде строки b (тоже из нулей и единиц, той же длины n). Менять строку b нельзя — это «образец».

С гирляндой a Егор может выполнять две операции:

• Переключить одну лампочку. Выбрать позицию i (1 ≤ i ≤ n) и поменять её состояние (0 → 1 или 1 → 0). Стоимость такой операции — 1 рубль.
• Поменять местами две лампочки. Выбрать две позиции i и j (1 ≤ i, j ≤ n) и поменять состояния этих лампочек местами. Стоимость такой операции — |i - j| рублей, то есть расстояние между позициями.

Помогите Егору найти минимальную суммарную стоимость, с которой можно превратить гирлянду a в гирлянду b.
 

Формат входных данных

В первой строке — целое число n (1 ≤ n ≤ 106) — количество лампочек в гирлянде.

Во второй строке — строка a длины n, состоящая только из символов «0» и «1», — текущее состояние гирлянды.

В третьей строке — строка b длины n, состоящая только из символов «0» и «1», — желаемое состояние гирлянды.
 

Формат выходных данных

Одно целое число — минимальная суммарная стоимость, которую нужно заплатить, чтобы превратить a в b.

Школьники приехали на экскурсию в новый город и решили осмотреть его достопримечательности. Представим город в виде прямоугольной сетки \(n \times m\), в некоторых клетках которой могут находиться достопримечательности.

Друзья начинают свой путь в клетке \((1, 1)\), они хотят дойти до клетки \((n,m)\), а затем вернуться обратно. В городе есть \(k\) достопримечательностей, они расположены в клетках \((x_1, y_1), \ldots, (x_k, y_k)\), друзья обязательно хотят посетить их все.

За одну минуту можно перейти из клетки \((a, b)\) в клетку \((c, d)\), если они являются соседними по стороне, то есть выполняется равенство \(|a - c| + |b - d| = 1\). Легко видеть, что на маршрут необходимо потратить хотя бы \(2n+2m-4\) минут, будем рассматривать только такие маршруты.

Будем называть маршрут интересным, если выполняются следующие условия:

• для того, чтобы пройти маршрут, друзья потратят ровно \(2n+2m-4\) минут;

• маршрут проходит через каждую клетку не более одного раза.

• маршрут проходит через все клетки, которые содержат достопримечательности.

Помогите школьникам понять, сколько существует различных интересных маршрутов. Так как это число может оказаться достаточно большим, то выведите его остаток при делении на \(10^9+7\).

В первой строке указаны числа \(n\), \(m\) и \(k\) (\(3 \le n,m \le 10^6\), \(0 \le k \le 2\,000\)).

В последующих \(k\) строках указано по паре чисел \(x_i\), \(y_i\) (\(1 \le x_i \le n\), \(1 \le y_i \le m\)), гарантируется, что все пары \((x_i, y_i)\) различны. То есть для любой пары индексов \((i, j)\) (\(1 \le i < j \le n\)) верно одно из двух: \(x_i \neq x_j\) или \(y_i \neq y_j\).

Выведите единственное число — остаток от деления числа интересных маршрутов на \(10^9+7\).

Ниже изображены все интересные маршруты для первого теста.

Рома, Саша и Алиса решили модернизировать знаменитый алгоритм шифрования RSA. Они считают, что ограничение на модуль \(n\), используемый в RSA, должно быть произведением двух различных простых чисел, избыточно. Вместо этого они планируют использовать \(n\), которое представляет собой произведение степеней \(k\) двух различных простых чисел: \(n = p^kq^k\).

Будем называть нетривиальным разложение числа \(n\) на множители, такое, что множителей хотя бы два, и каждый из них строго больше \(1\). Оказалось, что в случае \(n = p^kq^k\) у числа \(n\) может быть несколько различных нетривиальных разложений на множители. Например, \(100 = 2^2 5^2\) имеет восемь нетривиальных разложений: \(100 = 2\cdot 50\), \(100 = 2\cdot2\cdot25\), \(100 = 2\cdot2\cdot5\cdot5\), \(100=2\cdot5\cdot10\), \(100 = 4\cdot25\), \(100=4\cdot5\cdot5\), \(100=5\cdot20\) и \(100=10\cdot10\).

Теперь ребята задаются вопросом: пусть \(n = p^kq^k\), сколько существует различных нетривиальных разложений \(n\) на множители?

Формат входных данных
На вход подается одно целое число \(n\) (\(6 \le n \le 10^{18}\), гарантируется, что \(n=p^kq^k\) для двух различных \(p\) и \(q\) для целого \(k > 0\)).

Формат выходных данных
Выведите одно число "— количество нетривиальных разложений \(n\) на множители.

Дано неориентированное дерево "— связный граф из \(n\) вершин без циклов, и число \(k\). Зафиксируем некоторую вершину \(s\) дерева и назовем ее столицей.

Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро \((u, v)\) в направлении \(u \to v\), если при подвешивании дерева за вершину \(s\) вершина \(u\) является родителем вершины \(v\). Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы.

Определим расстояние до вершины \(v\) графа как минимальное количество ребер на пути из \(s\) в \(v\). Назовем доступностью вершины \(s\) максимальное из расстояний до всех вершин.

Разрешается добавить в дерево не более \(k\) дополнительных ориентированных ребер.

Для каждой вершины \(s\) дерева определите, какой минимальной доступности можно достичь, если выбрать вершину \(s\) в качестве столицы.

Обратите внимание, что в некоторых подзадачах требуется вывести ответ только для первой вершины.

Формат входных данных
Первая строка содержит три целых числа \(n\), \(k\) и \(t\) (\(2 \le n \le 2 \cdot 10^5\), \(1 \le k \le n - 1\), \(n \cdot k \le 2 \cdot 10^5\), \(0 \le t \le 1\)) — количество вершин дерева, ограничение на максимальное количество добавленных ребер и число \(t\), равное \(0\), если нужно вывести ответ только для вершины с номером \(1\), и равное \(1\) иначе.

Каждая из следующих \(n - 1\) строк содержит два целых числа \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) — ребра дерева.

Гарантируется, что заданные ребра образуют дерево.

Формат выходных данных

В случае, если \(t = 0\), выведите единственное целое число: минимальную доступность, которую можно достичь, выбрав вершину с номером \(1\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

В случае, если \(t = 1\), выведите \(n\) чисел: \(i\)-е число равняется минимальной доступности, которую можно достичь, выбрав вершину \(i\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

На рисунке приведены иллюстрации к первому примеру. Пунктирными линиями обозначены добавленные ребра. Для вершин \(1\) и \(2\) минимальная доступность равняется \(1\), а для вершин \(3\), \(4\) и \(5\) минимальная доступность равняется 2.