Description

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

Format

Input

给出 n个点（n个点是互异的），求出满足下列条件的连边方案：

1.不存在重边和自环。

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

Output

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

Samples

3

7