ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1309. Искусство спора

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Спор — великое дело. В споре рождается истина. Вот, например, два организатора чемпионата Урала поспорили. Один говорит, что на чемпионат по программированию давать задачи на подсчет функций глупо и бесполезно. И аргументирует это тем, что когда определение функции известно, и есть время на подготовку, можно очень быстро посчитать значение любой числовой функции в любой точке. А другой говорит, что не любая функция считается быстро, и додуматься ещё ведь надо. Конечно, за разногласия в стане жюри приходится расплачиваться участникам. И теперь Вам следует продемонстрировать, что Вы действительно способны быстро посчитать значение заданной функции в заданной точке.
Функция f(n) (n – целое) задана рекуррентно следующими формулами:
  • f(0) = 0,
  • f(n) = g(n, f(n-1)),
где g(x,y) = ((y-1)x5 + x3 – xy + 3x + 7y) % 9973, % означает операцию взятия остатка от деления на число.

Исходные данные

На входе в первой строчке находится единственное целое число n в диапазоне от 0 до 108.

Результат

На выход следует выдать единственное целое число: значение функции f(n). Причем сделать это очень быстро.

Пример

исходные данныерезультат
50
6300
Автор задачи: Идея — Александр Клепинин, подготовка — Александр Клепинин, Станислав Васильев
Источник задачи: VIII Командный студенческий чемпионат Урала по программированию. Екатеринбург, 11-16 марта 2004 г.