记录编号	367671	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__完全平方数	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.106 s
提交时间	2017-02-01 11:23:28	内存使用	81.35 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
const int MAXN = 5000001, MOD = 100000007;
bool vis[MAXN];
int primes[MAXN], jump[MAXN], id[MAXN], tot, cnt[MAXN];
void pre(int n){
  for(int i = 2; i <= n; i++){
    if(!vis[i]){
      primes[tot++] = i;
      id[i] = tot-1;
      jump[i] = 1;
    }
    for(int j = 0; j < tot; j++){
      int k = i*primes[j];if(k > n)break;
      vis[k] = true;
      jump[k] = i;
      if(i%primes[j] == 0)break;
    }
  }
}
typedef long long LL;
LL pow_mod(LL a, LL x){
  LL ans = 1;
  for(a %= MOD; x; x >>= 1, a = a*a%MOD)
    if(x&1)ans = ans*a%MOD;
  return (int)ans;
}
int main(){
  freopen("xnumber.in", "r", stdin);
  freopen("xnumber.out", "w", stdout);
  int n;scanf("%d", &n);
  pre(n);
  for(int i = 2; i <= n; i++){
    int t = i;
    while(t != 1){
      cnt[id[t/jump[t]]]++;
      t = jump[t];
    }
  }
  LL ans = 1;
  for(int i = 0; i < tot; i++)
    ans = ans*pow_mod(primes[i], cnt[i]&(~1))%MOD;
  printf("%lld\n", ans);
  return 0;
}