## Problem Description

Dumbear likes to play the Chinese Rings (Baguenaudier). It’s a game played with nine rings on a bar. The rules of this game are very simple:
1. At first, the nine rings are all on the bar.
2. The first ring can be taken off or taken on with one step.
3. If the first k rings are all off and the (k + 1)th ring is on, then the (k + 2)th ring can be taken off or taken on with one step. (0 ≤ k ≤ 7)
Now consider a game with N (N ≤ 1,000,000,000) rings on a bar, Dumbear wants to make all the rings off the bar with least steps. But Dumbear is very dumb, so he wants you to help him.

## Input

Each line of the input file contains a number N indicates the number of the rings on the bar. The last line of the input file contains a number “0”.

## Output

For each line, output an integer S indicates the least steps. For the integers may be very large, output S mod 200907.

## Sample Input

1
4
0

## Sample Output

1
10

## Source

Multi-School Training Contest - WHU Site #3