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≤x,y≤Nを満たすすべての点(x,y)におけるタイタニック集合Sの数をT(N)としよう。
T(1)=11, T(2)=494, T(4)=33554178, T(111)mod108=15300401, T(105)mod108=63259062であることが確かめられている。
T(1011)mod108を求めよ。