暂无测试数据。

背景

人世间所有的相遇都是久别重复，即使没有真正的遇见过彼此，但或许是在梦中。毕竟梦这种东西，醒来之后就会消失的。

享受梦境吧，或者珍惜每一个相遇的人，或者告诉我你的名字吧！

描述

话说Achen副宗主为理想倒在了殇阳关面前，XYJ见状（Rank2%%）赶紧偷走了Achen的时空机，并迅速穿越到了女儿国

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

题目简述：
给出 n个点（n个点是互异的），求出满足下列条件的连边方案：
1.不存在重边和自环。
2.不存在三个点a，b，c使三个点间两两距离相等。

格式

输入格式

一个整数n

输出格式

一个整数，表示方案数对1004535809取模的结果。

样例1

样例输入1

3

样例输出

7

样例解释

**相信大家都觉得这是道水题，所以SummerWang就懒得解释了，快爆发你的小宇宙，帮一帮Rank2 XYJ吧！

限制

每个测试点1s，共20个测试点
对于10%的测试数据，n<=9
对于50%的测试数据，n<=2000
对于80%的测试数据，n<=100000
对于100%的测试数据，n<=1000000

后记

XYJ泡到妹子后，是否会大发善心，去殇阳关救救那可怜的Achen呢？（未完待续）。

来源

Summer_Wang改编自FJMTC2015