Ширина последовательности

Районная олимпиада школьников Удмуртии по программированию, 2009 год

Последовательность формируется по следующему алгоритму:

X₁ — задаётся.
X_i+1 = (X_i « 1) + 2009

Вычислить разницу между самым большим и самым маленьким числами последовательности.

Технические требования

Операция A « B означает, перенос последней десятичной цифры числа A вперёд B раз. Например, 12340 « 3 = 3412.

0 < X₁ < 1 000 000

Последнее число в последовательности имеет номер 10 000 000. Т.е. последовательность X₁…X_10000000

Задаётся строка длиной не более 100 символов.

Пример

X1= 100
Разница: 9990971

Время работы программы 1 секунда