Дана непустая последовательность из букв «a», «b» и «c». Требуется посчитать количество способов выбрать две различные буквы в последовательности (то есть две разные по значению буквы, одинаковые буквы на разных позициях выбирать не разрешается) и поменять их местами, чтобы получившаяся последовательность была правильной.

Правильная последовательность букв определяется следующим образом:

• Пустая последовательность является правильной.
• Если A — правильная последовательность, то aAa, bAb и cAc также являются правильными.
• Если A и B — правильные последовательности, то AB (конкатенация A и B) также правильная.
• Последовательности, которые невозможно получить при помощи операций, описанных выше, не являются правильными.

Даны массив a длины n, и массив b длины m. Все элементы обоих массивов — цифры от 0 до 9 включительно. Составим по этим массивам таблицу c размера n × m, где элемент в i-й строке и j-м столбце определяется формулой c_i, j = a_i·10⁹ + b_j.

Рассмотрим всевозможные пути из клетки c_1, 1 в клетку c_n, m, состоящие только из перемещений вниз и вправо (то есть, из клетки c_i, j можно переходить только в клетки c_{i + 1, j} и c_{i, j + 1}, если эти клетки находятся внутри таблицы). Среди всех этих путей выберите такой, что сумма чисел в посещённых клетках максимальна, и выведите эту сумму.

Рома играет в новую версию World of Darkraft за персонажа-мага. Рома ценит своё игровое время и старается выполнять внутриигровые задания как можно эффективнее.

Сейчас Рома сражается с n монстрами. i-й из этих монстров имеет h_i очков здоровья. Монстр погибает, если его очки здоровья становятся равными нулю или отрицательными (в этот момент Ромин персонаж получает опыт).

Запас маны Роминого персонажа составляет m единиц. Персонаж владеет двумя заклинанями: «Удар молнии» и «Кольцо льда».

• «Удар молнии» наносит d_s единиц урона выбранному монстру (то есть уменьшает количество его очков здоровья на d_s), и одно применение этого заклинания стоит c_s единиц маны.
• «Кольцо льда» наносит d_a единиц урона всем ещё живым монстрам, и одно применение этого заклинания стоит c_a единиц маны.

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

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

В чемпионате Берляндии по многоборью участвуют n спортсменов. Соревнование состоит из k этапов, на каждом из которых участник может набрать любое вещественное число очков в диапазоне от 0 до 1.

Маленький мальчик Олег любит спортивную аналитику, и поэтому хочет осветить чемпионат в своём спортивном блоге. Олег ничего не знает ни про спортсменов, ни про ход соревнования. Зато Олег знаком с теорией вероятностей, поэтому он предполагает, что каждый спортсмен на каждом этапе набирает случайное число очков, равномерно распределенное на отрезке [0, 1]. Также Олег считает, что результаты всех спортсменов на всех этапах в совокупности независимы.

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

Обратите внимание, что в справедливой таблице один спортсмен может стоять выше другого, даже если он проиграл ему на всех этапах. Пусть, например, в соревновании из двух этапов очки спортсмена 1 равны (0.2, 0.2), очки спортсмена 2 равны (0.8, 0.8), а очки спортсмена 3 равны (0, 1). Тогда таблица (1, 3, 2) является справедливой, поскольку спортсмен 1 обогнал спортсмена 3 на первом этапе, а спортсмен 3 обогнал спортсмена 2 на втором; при этом спортсмен 1 проиграл спортсмену 2 на каждом из этапов.

Чемпионат еще не начался, но Олег уже хочет зарезервировать достаточно места на хостинге, чтобы все таблицы поместились на сервер. Для этого он просит вас посчитать математическое ожидание количества способов составить справедливую рейтинговую таблицу по итогам соревнований. Олег также хочет проверить свои навыки в теории чисел, поэтому он хочет получить ответ по модулю P = 998 244 353. Формально, если ответ на задачу представленный в виде несократимой дроби равен A / B, вам следует вывести такое целое число x, что 0 ≤ x < P и A ≡ B·x ± od P (гарантируется, что такое число x существует и единственно).

Математическое ожидание величины, принимающей целые значения, определяется как , где суммирование происходит по всем целым числам, а p_x — вероятность того, что величина принимает значение x.

Василий увлекается бонсай — искусством выращивания декоративных деревьев. У него есть два красивых дерева, но эстетическое чутьё Василия подсказывает ему, что эти деревья нужно сделать как можно более похожими.

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

Василий может совершать два типа операций с любым из деревьев:

• Удалить из дерева любой лист — вершину, из которой не исходит ни одного ребра. Корень дерева удалять ни в коем случае нельзя.
• Выбрать два соседних ребра, исходящих из одной вершины, и аккуратно связать их верёвочкой. После этого Василий считает, что два данных ребра становятся одним ребром, а концы этих рёбер становятся одной вершиной, из которой исходят все рёбра, ранее исходившие из начал связанных рёбер. Порядок рёбер, исходящих из новой вершины определяется так: сперва все рёбра, исходившие из конца левого связанного ребра, а затем все рёбра, исходившие из конца правого связанного ребра. Относительный порядок рёбер при этом не меняется. Полученные в результате связывания вершины и рёбра считаются обычными вершинами и рёбрами и могут участвовать в дальнейших связываниях и удалениях.

Василий считает, что деревья стали одинаковыми, если можно построить взаимно-однозначные соответствия между рёбрами и между вершинами двух деревьев таким образом, что:

• Из соответствующих друг другу вершин исходит одинаковое количество рёбер, и все эти рёбра сопоставлены друг другу согласно их порядку.
• Для соответствующих друг другу рёбер их концы сопоставлены друг другу.

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

Разумеется, Василий хочет как можно меньше испортить исходные деревья. Какое минимальное количество операций ему придется совершить с деревьями, чтобы они стали одинаковыми?

Математики Альфред и Георг играют в игру. Они берут белый клетчатый листок размером n × m клеток. Сначала Альфред раскрашивает некоторые клетки в чёрный цвет, после чего Георг должен снова перекрасить все клетки в белый. Для этого Георг сколько угодно раз проделывает следующую операцию:

• Поместить карандаш в левый нижний угол листка (будем считать, что это точка с координатами (0, 0)), после чего нарисовать путь в верхний правый угол листка (точку с координатами (n, m)). Путь должен проходить только по границам клеток, кроме того, передвигать карандаш можно только вправо и вверх, то есть из позиции (x, y) карандаш можно передвинуть только в позиции (x + 1, y) и (x, y + 1), если при этом карандаш не покинет пределом листка.
• Перекрасить все клетки листка, расположенные под нарисованным путём, в противоположный цвет (то есть, все белые клетки под путём перекрасить в чёрный цвет, а все чёрные — в белый). После этого нарисованный путь стирается, и (если это необходимо) Георг переходит к следующей операции.

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