#1185. Tibbar的后花园

Tibbar的后花园

Description

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

Format

Input

给出 n个点(n个点是互异的),求出满足下列条件的连边方案:

1.不存在重边和自环。

2.不存在三个点a,b,c使三个点间两两距离相等。

Output

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

Samples

3
7