Спор — великое дело. В споре рождается истина. Вот, например, два организатора чемпионата Урала поспорили. Один говорит, что на чемпионат по программированию давать задачи на подсчет функций глупо и бесполезно. И аргументирует это тем, что когда определение функции известно, и есть время на подготовку, можно очень быстро посчитать значение любой числовой функции в любой точке. А другой говорит, что не любая функция считается быстро, и додуматься ещё ведь надо. Конечно, за разногласия в стане жюри приходится расплачиваться участникам. И теперь Вам следует продемонстрировать, что Вы действительно способны быстро посчитать значение заданной функции в заданной точке.

Функция f(n) (n – целое) задана рекуррентно следующими формулами:

• f(0) = 0,
• f(n) = g(n, f(n-1)),

где g(x,y) = ((y-1)x⁵ + x³ – xy + 3x + 7y) % 9973, % означает операцию взятия остатка от деления на число.

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

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