Задача 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), у другому - кількість заборонених слів K (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

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

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