版权声明

本题版权归 CTFPC 出题组 所有。

题目背景

DFbd 在卷题……

题目描述

DFbd 正在卷题，可是他被难住了，请你帮帮他。

给定质数 $p$，求：

$$\left( \prod\limits_{i = 1}^{p - 1}\prod\limits_{d \mid i} d \right) \mod p$$

输入格式

一行一个质数 $p$。

输出格式

一行一个整数，表示答案。

样例

3

2

7

2

数据范围

Subtask	$p \le$	特殊性质	分值	依赖子任务
0	$7$	是样例	0	-
1	$10^4$	无	40	0
2	$10^7$		60	0, 1

对于 $100\%$ 的数据，$3 \le p \le 10^7$ 且 $p$ 是质数。