Задача Algo. Исполнитель Робот может двигаться по клетчатой дорожке, выполняя шаги вперед или назад по таким правилам, последовательность которых задает «правильный» алгоритм его движения:

- Команда ВПЕРЕД (U) - робот делает U шагов вперед. Такая команда должна быть в «правильном» алгоритме всегда первой и всегда последней. В процессе выполнения алгоритма эта команда может выполняться несколько раз подряд.

- Команда НАЗАД (D) - робот делает D шагов назад. Такую команду можно выполнять только между двумя командами ВПЕРЕД (U), то есть она не может быть выполнена несколько раз подряд. В пределах одного алгоритма команда НАЗАД (D) может быть выполнена с различными D (1 <= D <= U-1). За пределы дорожки робот выходить не может, а стартует с первой клеточки. Сколько разных «правильных» алгоритмов могут составить кружковцы для робота? Понятно, что каждый "правильный" маршрут завершается на последней клетке дорожки.

Технические условия. Программа Algo читает с устройства стандартного ввода 2 числа через пробел: U - количество шагов в команде ВПЕРЕД (U), и N - длину клетчатой дорожки (2 <= U <= N <= 1000000). Программа выводит на устройство стандартного вывода единственное число - количество «правильных» последовательностей команд. Так как их количество может быть велико, выводить по модулю 1000000. Если одни и те же команды размещены в разной последовательности (обе - по правилам!) - это разные алгоритмы.

Примеры

Задача Kingdoms. В одном далеком сказочном королевстве жил Ученый. Много лет он работал над возможностью путешествовать другими сказочными королевствами, находящихся в параллельных мирах. Вследствие проведенных многочисленных экспериментов и по счастливой случайности Ученый вдруг обнаружил, что осуществить свою давнюю мечту можно с помощью портального устройства, собранного из волшебных кристаллов. Существует всего девять разновидностей таких кристаллов, причем кристаллы каждого из девяти видов есть в королевстве в достаточном количестве. Для того, чтобы попасть в сказочное королевство, которое находится в параллельном мире номер N, надо последовательно (плотно друг к другу в ряд) соединить ровно N волшебных кристаллов таким образом, чтобы оптическое увеличение полученного портального устройства численно равнялось его электрическому сопротивлению. Помогите Ученому определить, сколько существует различных способов попасть в параллельный мир номер N и какое минимальное количество волшебных кристаллов каждого вида для этого понадобится.

Величины оптического увеличения и сопротивления каждого из девяти видов кристаллов численно равны их номерам - от одного до девяти. Например, оптическое увеличение всех волшебных кристаллов "номер шесть" равна шести и электрическое сопротивление их также равна шести. Путешествия совершаются поочередно, кристаллы можно использовать многократно.

Технические условия. Программа Kingdoms читает с устройства стандартного ввода натуральное число N (1 <= N <= 500). Программа выводит в одной строке через пробелы сначала искомое число - количество различных способов попадания в параллельный мир с заданным номером, а дальше девять чисел - минимальное количество кристаллов (в порядке увеличения номеров) для осуществления всех последовательных путешествий в параллельный мир номер N.

Задача Censure. В стране Триляндии азбука состоит из первых N маленьких английских букв, а по указу Президента все слова пишутся без пропусков. Границы слов можно устанавливать произвольно, но некоторые (возможно и все) слова, которые состоят из трех букв Министерство Цензуры запретило для использования. Найдите количество триляндских предложений, не содержащих ни одного запрещенного слова (то есть «цензурных»).

Технические условия. Программа Censure читает с устройства стандартного ввода в первой строке количество букв в триляндской азбуке N (2 <= N <= 26), во второй - количество запрещенных слов К(0<=K<=N³) и в третьей- длину предложения L (3 <= L <= 1000). Далее следует K строк, в каждой из которых содержится запрещенное слово из трех букв. Все слова разные. Программа выводит количество «цензурных» предложений по модулю 1000000007.

Пример

Ввод

3

8

4

aaa

abc

aab

aac

aba

abb

aca

cca

Вывод

40

Задача Glamur. В батальон Гламур набрали N² солдат, все они имели разный рост, представленный целыми числами от 1 до N². На занятиях по ориентированию на местности (как же без этого!) Главный Командующий дал солдатам приказ выстроиться на квадратном, размеченном N*N клеток плацу, клетки которого ориентированы по сторонам света. В приказе говорилось:

- в каждой шеренге, которые выстраиваются вдоль линии «восток-запад», рост солдат с запада на восток увеличивается;

- В каждой колонне, которые выстраиваются вдоль линии «север - юг», рост солдат с севера на юг увеличивается;

- суммарный рост солдат, стоящих по периметру плаца (во всех крайних клетках) был наименьшим. Что увидел Главный Командующий?

Технические условия. Программа Glamur читает с устройства стандартного ввода единственное целое число N (1 <= N <= 100). Программа выводит N строк по N чисел (рост солдат, стоящих в соответствующей ячейке), конечно, при условии строгого выполнения приказа.

Пример.

Ввод

3

Вывод

1 2 4

3 6 8

5 7 9

Задача Glass. Автор задачи предлагает почувствовать себя физиком и провести эксперимент. Итак:

У вас есть шарик радиусом r и плотностью w, которую вы за невесомую нерастяжимую нить медленно опускаете в цилиндрический стакан радиусом R (R <> r) и высотой H, который неподвижно стоит на бесконечной горизонтальной плоскости. В стакан наливаете h (h <= H) воды, плотностью 1. В области проведения эксперимента действует однородное гравитационное поле, ориентированное вниз. Плотностью воздуха и поверхностным натяжением пренебрегаем. Стакан имеет бесконечно тонкие, жесткие стенки, шарик не деформируется, вода не сжимается. Напишите программу, которая определит, сколько шарика по высоте окажется под водой после того, как шарик перестанет погружаться. (см. рисунок)

Технические условия. Программа GLASS считывает со стандартного устройства ввода 5 разделенных пробелами действительных чисел R, H, w, r, h, которые принадлежат промежутку 10^-3; 10³ .Программа выводит на стандартный вывод единственное действительное число - искомую высоту Х. Результат не округляйте.

Пример

Ввод

2 10 0.5 1 5

Вывод

0,9999999999999

========================================================================

Задания подготовили И. Энтин, Г. Непомнящий, Ю. Пасихов, И. Порубльов, Д. Полищук.