A set of integral lattice points S is called an epic set if there exists a line L such that L passes through exactly two points in S.

Consider the following example: S = {(0,0), (0,1), (1,0), (1,1), (2,1)} is an epic set because the line x = 0 passes through only (0,0) and (0,1).

Similarly, the set T = {(0,0), (0,1), (0,2), (0,3)} is not an epic set because the points are collinear, i.e., there exists no line that passes through only 2 points of the set.

So for any positive integer N, we define the function E(N) to be the epic number of N. The epic number of N is the number of epic sets S that can be formed, such that every point (x,y) of S satisfies 0 <= x, y <= N.

Input: A list of positive integers, N such that 0 <= N <= 100000 (One per line). Stop when you encounter -1.

Output: The value of epic numbers of each of the values of N, i.e., E(N) mod 10^8 (One per line).