Problem 415
Titanic sets
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 108 = 13500401 and T(105) mod 108 = 63259062.
Find T(1011) mod 108.
泰坦尼克集
格点集S被称为泰坦尼克集，如果存在一条直线恰好只穿过S中的两个点。
泰坦尼克集的一个例子是S = {(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)}，存在直线穿过点(0, 1)和点(2, 0)，而不穿过S中其它的点。
相反的，集合{(0, 0), (1, 1), (2, 2), (4, 4)}不是泰坦尼克集，因为穿过集合中任意两点的直线也穿过集合中另外的两个点。
对于任意正整数N，记T(N)为所有可能的泰坦尼克集S的数目，要求S中所有的点(x, y)满足0 ≤ x, y ≤ N。可以验证T(1) = 11, T(2) = 494, T(4) = 33554178, T(111) mod 108 = 13500401以及T(105) mod 108 = 63259062。
求T(1011) mod 108。