Задача Algo. Виконавець Робот може рухатися по клітчастій доріжці, виконуючи кроки вперед чи назад за такими правилами, послідовність яких задає «правильний» алгоритм його руху:
- команда ВПЕРЕД(U) – робот робить U кроків вперед. Така команда повинна бути у«правильному» алгоритмі завжди першою і завжди останньою. У процесі виконання алгоритму ця команда може виконуватися кілька разів поспіль.
- команда НАЗАД(D) - робот робить D кроків назад. Таку команду можна виконувати лише між двома командамиВПЕРЕД(U), тобто вона не може бути виконана кілька разів підряд. В межах одного алгоритму командаНАЗАД(D) може бути виконана з різними D (1<=D<= U-1). За межі доріжки робот виходити не може, а стартує з першої клітинки.Скільки різних «правильних» алгоритмів можуть скласти гуртківці для робота? Зрозуміло, що кожен "правильний" маршрут закінчується на останній клітинці доріжки.
Технічні умови. Програма Algo читає з пристрою стандартного введення 2 числа через пропуск: U - кількість кроків у команді Вперед(U), та N – довжину клітчастої доріжки (2<=U<=N<=1000000). Програма виводить на пристрій стандартного виведення єдине число – кількість «правильних» послідовностей команд. Так як їх кількість може бути велика, виводити по модулю 1000000 Якщо одні й ті ж самі команди розміщено в різній послідовності (обидві – за правилами!) – це різні алгоритми.
Приклади
|
Введення 3 7 |
Введення 5 15 |
|
Виведення 4 |
Виведення 236 |