1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

 private static long MOD = 1000000007;  // 定义模数常量，用于取模运算
    private static List<Long> mList = new ArrayList<>();  // 存储欧拉函数值的列表

    /**
     * 主方法，处理输入输出并计算结果
     *
     * @param args 命令行参数
     * @throws IOException 可能抛出IO异常
     */
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取输入的长整型数值n
        long n = Long.parseLong(br.readLine().trim());

        // 初始化tmp为MOD值，并添加到mList列表中
        long tmp = MOD;
        mList.add(tmp);

        // 计算欧拉函数值直到tmp为1，并将结果添加到mList中
        while (tmp > 1) {
            tmp = getPhi(tmp);
            mList.add(tmp);
        }

        // 调用solve方法计算结果并输出，取模MOD
        out.println(solve(n, 0) % MOD);


        // 清空输出缓冲区并关闭资源
        out.flush();
        out.close();
        br.close();
    }

    /**
     * 递归求解模幂运算的结果
     *
     * @param curN 当前处理的数字
     * @param idx  当前处理的mList中的索引位置
     * @return 返回模幂运算的结果
     */
    private static long solve(long curN, int idx) {
        // 获取当前索引对应的模数
        long m = mList.get(idx);
        // 如果模数为1，任何数对1取模结果都是1
        if (m == 1) {
            return 1;
        }

        // 如果当前数字为1，1的任何次幂都是1
        if (curN == 1) {
            return 1;
        }

        // 递归计算指数部分，curN-1和idx+1表示递归处理下一个数字和下一个模数
        long exp = solve(curN - 1, idx + 1);

        // 计算curN的exp次幂对m取模的结果
        return safePow(curN, exp, m);
    }

    /**
     * 安全的幂运算函数，计算 a^b mod m，并处理可能的溢出情况
     *
     * @param a 底数
     * @param b 指数
     * @param m 模数
     * @return 计算结果，如果发生溢出则返回结果加上模数后的值
     */
    private static long safePow(long a, long b, long m) {
        long res = 1;        // 初始化结果为1
        boolean overflow = false;  // 溢出标志，初始为false

        // 如果底数大于等于模数，进行取模操作，并标记可能溢出
        if (a >= m) {
            overflow = true;
            a %= m;
        }

        // 使用快速幂算法计算幂运算
        while (b > 0) {
            // 如果当前指数的二进制最低位为1（即指数为奇数）
            if ((b & 1) == 1) {
                res = res * a;   // 将当前底数乘入结果
                // 如果结果大于等于模数，进行取模操作，并标记可能溢出
                if (res >= m) {
                    overflow = true;
                    res %= m;
                }
            }

            b >>= 1;   // 指数右移一位，相当于除以2
            // 如果指数还有剩余位
            if (b > 0) {
                a = a * a;   // 底数平方
                // 如果平方后的底数大于等于模数，进行取模操作，并标记可能溢出
                if (a >= m) {
                    overflow = true;
                    a %= m;
                }
            }
        }
        // 根据溢出标志返回结果，如果溢出则加上模数
        return overflow ? (res + m) : res;
    }

    /**
     * 计算欧拉函数Phi(n)的值
     * 欧拉函数Phi(n)表示小于n的正整数中与n互质的数的个数
     *
     * @param n 需要计算欧拉函数的正整数
     * @return 返回n的欧拉函数值
     */
    private static long getPhi(long n) {
        long res = n;  // 初始化结果为n

        // 遍历2到sqrt(n)的所有整数
        for (long i = 2; i * i <= n; i++) {
            // 如果i是n的因数
            if (n % i == 0) {
                // 应用欧拉函数的公式：res = res * (1 - 1/p)
                res = res / i * (i - 1);
                // 去除n中所有的i因子
                while (n % i == 0) {
                    n /= i;
                }
            }
        }

        // 如果n大于1，说明n本身是一个质数
        if (n > 1) {
            res = res / n * (n - 1);
        }
        return res;
    }