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 10^8 = 13500401 and T(10^{5}) mod 10^8 = 63259062.

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

一个整点集合S称为Titanic Sets当且仅当存在一条直线恰好经过其中两个点。
定义T（N）为每个点都满足0<=x,y<=N的Titanic Sets个数，输入N(N<=10^11)输出T(N)

---

输入格式

---

输出格式

---

样例输入

3

---

样例输出

65465

---

提示

没有写明提示

---

题目来源

没有写明来源