N is a base ten positive integer formed by writing the digit 7 precisely 2010 times, that is N = 77....77 (2010 times).

Determine the

**digital root** of [N/199].

__Note__: [x] denotes the greatest integer ≤ x.

*** For an extra challenge, solve this problem without using a computer program.

N mod 9 is easy to compute: N mod 9 = 2010*7 mod 9 = 21*7 mod 9 = 3.

N mod 199 is trickier without a computer. First express N as a sum:

N = Sigma{i=0 to 699} 777*1000^i

777 mod 199 = 180, 1000 mod 199 = 5. Then:

N = Sigma{i=0 to 669} 180*5^i mod 199

The closed form of this sum is:

N = 180*(5^670 - 1)/4 mod 199

Since 199 is prime Fermat's Little Theorem implies x^198 = 1 mod 199. With 670 = 3*198+76, this implies:

N = 45*(5^76-1) mod 199

This is small enough to evaluate by hand. Then N = 186 mod 199.

From the Chinese Remainder Theorem: N mod (9*199) = 199*3 + 9*87 = 1380.

Then floor[N/199] mod 9 = floor[1380/199] mod 9

1380 = 6*199 + 186 and 199 mod 9 = 1. Therefore floor[N/199] mod 9 = 6*1 = **6**.