如果存在一条直线恰好穿过 $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)$为每个点$(x,y)$满足$0\le x,y\le N$的泰坦尼克集$S$的数量。 可以验证 $T(1)=11$、$T(2)=494$、$T(4)=33554178$、$T(111)mod{10}^8=13500401$ 和 $T({10}^5)mod{10}^8=63259062$。

求 $T({10}^{11})mod{10}^8$。