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\le x,y\le N$. It can be verified that $T(1)=11$, $T(2)=494$, $T(4)=33554178$, $T(111)mod{10}^8=13500401$ and $T({10}^5)mod{10}^8=63259062$.

Find $T({10}^{11})mod{10}^8$.