Titanic Sets
题目描述
若平面上的一个有限整点集合 S 存在一条直线恰好经过其中两个点,就称 S 为 Titanic 集合。直线可以穿过其他未被选入 S 的整点。
例如,集合 {(0,0),(0,1),(0,2),(1,1),(2,0),(1,0)} 是 Titanic 集合:经过 (0,1) 和 (2,0) 的直线不经过该集合中的其他点。相反,集合 {(0,0),(1,1),(2,2),(4,4)} 不是 Titanic 集合:这四个点共线,任意过其中两点的直线也经过另外两点。
给定正整数 N,设 T(N) 为从全部满足 0≤x,y≤N 的整点中选出一个 Titanic 集合的方案数。求 T(N) 对 108 取模后的结果。
输入格式
输入一行一个正整数 N。
输出格式
输出一行一个整数,表示 T(N)mod108。
样例
样例输入 #1
3
样例输出 #1
65465
数据范围
1≤N≤1011。例如,T(1)=11,T(2)=494,T(4)=33554178;T(111)mod108=13500401,T(105)mod108=63259062。