Злий професор тільки що задав Вам наступну задачу. Визначимо послідовність наступним чином:
Для кожного значення i обчисліть xi.
Вхідні дані містять декілька рядків, кожен з яких містить одне ціле число — значення i, яке не менше 0 і не більше 106. Останній рядок містить −1 та не обробляється.
Для кожного значення i (крім останнього −1), виведіть відповідне значення xi,обчислене за модулем 106.