Can you find it?

A set of lattice points S is called a titanic set if there exists a line passing through exactly two points in S.

An example of a titanic set is S = {(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)}, where the line passing through (0, 1) and (2, 0) does not pass through any other point in S.

On the other hand, the set {(0, 0), (1, 1), (2, 2), (4, 4)} is not a titanic set since the line passing through any two points in the set also passes through the other two.

For any positive integer N, let T(N) be the number of titanic sets S whose every point (x, y) satisfies 0 ≤ x, y ≤ N.

It can be verified that T(1) = 11, T(2) = 494, T(4) = 33554178, T(111) mod (10⁸) = 13500401 and T(10⁵) = 63259062.

Find T(10¹¹) mod 10⁸.

...why is T(1) = 11 ?

oh, i think i get it..

T(0) = 1 ? =)

no no t(0)=0 because no duplicates...

actually sounds pretty easy once you get over the size of the grid..

for each point A
  for each point B > A
    all combinations of points not on line A-B

...try doing it so that there are not more than two points on any line ;D