"Длинная" арифметика

Напишите программу, вычисляющую остаток от деления заданного «длинного» числа на заданную цифру.

Входные данные
В первой строке задана цифра K (1≤K≤9). Во второй строке задано натуральное число N, состоящее из не более чем 250 цифр.

Выходные данные
Выведите остаток от деления N на K.

Напишите программу, вычисляющую остаток от деления заданного «длинного» числа на заданную цифру.

Входные данные
В первой строке задана цифра K (1≤K≤9). Во второй строке задано натуральное число N, состоящее из не более чем 100000 цифр.

Выходные данные
Выведите остаток от деления N на K.

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

• знак числа (пишется только в случае, когда его отсутствие изменяет число);
• целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
• пробел (не пишется, если отсутствует целая или дробная часть);
• числитель (если он не равен нулю);
• знак / (если есть числитель);
• знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.

Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю.

Входные данные
В первой строке вводится дробь (первый операнд), во второй - знак операции ("+" - сложение, "-" - вычитание, "*" - умножение, "/" - деление), в третьей строке - дробь (второй операнд). Обе дроби могут быть сократимы.

Выходные данные
В единственной строке выводится несократимая правильная дробь (результат) в описанном формате.

Дано целое неотрицательное число в I-ричной системе счисления. Вывести это число в J-ричной системе счисления.

Входные данные
В первой строке находятся числа I и J (в десятичной системе счисления), во второй строке - число для перевода. 2 <= I, J <= 36, для представления цифр 10...35 используются прописные латинские буквы A...Z
 соответственно, число разрядов исходного числа не превышает 1000.

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

Даны целое неотрицательное число M и целое положительное число N. Найти M div N и M mod N.

Входные данные
В первой строке находится число M, во второй - N. 0 <= M <= 10⁶⁰⁰⁰⁰, 1 <= N <= 1 000 000.

Выходные данные
В первой строке вывести значение выражения M div N во второй - выражения M mod N.

Даны целые неотрицательные числа M и N. Найти M*N.

Входные данные
В первой строке находится число M, во второй - N. 0 <= M, N <= 10²⁵⁰⁰.

Выходные данные
Вывести одно число - результат умножения.

Даны два целых неотрицательных числа: M и N. Найти их сумму.

Входные данные
В первой строке содержится M, во второй - N. 0 <= M, N < 10³⁰⁰⁰⁰.

Выходные данные
В первой строке вывести сумму без пробелов и ведущих нулей.

Для натуральных чисел a и n вычислить aⁿ.

Входные данные
В первой строке находятся разделённые пробелом a и n. 1 <= a <= 9, 1 <= n <= 7000.

Выходные данные
Выводится одно число - результат без стоящих впереди нулей, стоящих впереди и позади пробелов.

Крупная межгалактическая сеть мебельных магазинов Galactic-Мебель недавно вышла на рынок мебели для кухонь в звездной системе LoST-2007. В этой звездной системе во всех квартирах кухни имеют форму прямоугольника размером a на b метров. При этом вдоль одной из стен принято ставить стол, в смежной с ней стене находится окно. Таким образом, для размещения различных кухонных шкафчиков остается угол со сторонами a и b метров.

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

В звездной системе LoST-2007 используется n типов кухонных шкафчиков. Каждый тип шкафчиков характеризуется своей шириной wi, при этом на кухне должен присутствовать ровно один экземпляр каждого типа шкафчиков.

Недавно директор маркетингового отдела Galactic-Мебель заметил, что он может предложить клиентам несколько вариантов расположения шкафчиков на кухне. Различными считаются варианты, которые отличаются расположением хотя бы одного шкафчика. При этом шкафчики различных типов могут иметь одинаковую ширину, однако отличаются внешней отделкой. Так что даже размещения, которые отличаются лишь позициями шкафчиков с равной шириной, считаются различными. Например, пусть a = 3, b = 4 и есть два типа шкафчиков, шириной 1 и 2, соответственно.


Тогда возможно шесть планировок кухни. Возможные планировки показаны на рисунке.

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

Входные данные
Первая строка содержит три целых числа: a, b и n (1 ≤ a ≤ 300, 1 ≤ b ≤ 300, 1 ≤ n ≤ 100). Каждая из следующих n строк содержит целое число w_i (1 ≤ w_i ≤ 300) — ширину соответствующего шкафчика.

Выходные данные
Выведите количество различных планировок кухни.

Широкое распространение в стандартных библиотеках многих языков программирования получила реализация сбалансированных деревьев на основе так называемых красно-черных деревьев. В данной задаче вам предлагается посчитать количество красно-черных деревьев заданной формы.

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

Если вершина \(Y\) — ребенок вершины \(X\), то говорят, что вершина \(X\) является родителем вершины \(Y\). У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

Соединим каждую вершину кроме корня с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.

Двоичное дерево называется красно-черным, если каждая его вершина раскрашена в красный либо в черный цвет, причем выполняются следующие условия:

1. если вершина красная, то ее родитель — черный;

2. количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.

Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке.

Если считать закрашенные вершины черными, а незакрашенные — красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) — нет. Для дерева на рисунке (б) нарушается первое свойство — у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство — на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 — две.

Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин в дереве (\(1 \le n \le 1000\)).

Пусть вершины дерева пронумерованы числами от \(1\) до \(n\). Следующие \(n\) строк содержат по два числа — для каждой вершины заданы номера ее левого и правого ребенка. Если один из детей отсутствует, то вместо его номера записан ноль. Гарантируется, что входные данные корректны, то есть набор чисел действительно задает двоичное дерево.

Формат выходных данных
Выведите одно число — количество способов раскрасить вершины заданного во входном файле двоичного дерева в красный и черный цвета так, чтобы оно стало красно-черным деревом.

Все допустимые способы раскрасить вершины дерева из первого примера приведены на следующем рисунке.