415 : タイタニック集合

格子点の集合Sについて、そのうちの2点のみを通る直線が存在するとき、その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)} はタイタニック集合ではない。 なぜなら集合内のいかなる2つの点を通る直線も他の2つの点を通るからである。

ある正の整数$N$に対して、$0 \leq x, y \leq N$を満たすすべての点$(x,y)$におけるタイタニック集合Sの数を$T(N)$としよう。

$T(1) = 11$, $T(2) = 494$, $T(4) = 33554178$, $T(111) \bmod 10^8 = 15300401$, $T(10^5) \bmod 10^8 = 63259062$であることが確かめられている。

$T(10^{11}) \bmod 10^8$を求めよ。