#4228. Tibbar的后花园

内存限制:512 MiB 时间限制:40 Sec

题目描述

Tibbar有许多妹子,他将妹子们安排在一个巨大的后花园,每个妹子居住在一间小木屋中。为了方便自己泡妹子,他决定将妹子们所在的木屋通过道路连接起来。然而Tibba有选择困难症,若出现三个妹子间距离两两相等,他便会纠结该去和哪个妹子聊天,然后开始数叶片,抛硬币,点绵羊,虚度人生……为了避免上述事件发生,修道路这件任务就交给你了,首先你要求出有多少种可行方案。注意,妹子和妹子是不一样的。

输入格式

给出 n个点(n个点是互异的),求出满足下列条件的连边方案:
1.不存在重边和自环。
2.不存在三个点a,b,c使三个点间两两距离相等。

输出格式

一个整数n。一个整数,表示方案数对1004535809(479*2^21+1,质数)取模的结果。

样例

样例输入


			
3

样例输出


			
7

数据范围与提示