#include <iostream>
using namespace std;
int phi[1000005], prime[1000005]; bool is_prime[1000005];
long long qp(long long n, long long m, long long p) {
    long long ans = 1, base = n;
    while (m) {
        if (m & 1) (ans *= base) %= p;
        (base *= base) %= p; m >>= 1;
    }
    return ans;
}
void pre() {
  for (int i = 1; i <= 1000000; i++) {
    is_prime[i] = 1;
  }
  int cnt = 0;
  is_prime[1] = 0;
  phi[1] = 1;
  for (int i = 2; i <= 1000000; i++) {
    if (is_prime[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= 1000000; j++) {
      is_prime[i * prime[j]] = 0;
      if (i % prime[j])
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      else {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}
int main() {long long n; pre();
//for (int i=1; i<=1000000; i++) phi[i] = i;
//for (int i=2; i<=1000000; i++) if (phi[i] == i) for (int j=i; j<=1000000; j+=i) phi[j] = (phi[j] / i) * (i - 1);
for (int i=1; i<=1000000; i++) (phi[i] += phi[i-1]) %= 104857600; long long prod = 1; cin >> n; for (int i=1; i<=n; i++) (prod *= i) %= 104857601; prod = qp(prod, 2 * n, 104857601); for (int i=1; i<=n; i++) {(prod *= qp(qp(i, 2 * phi[n/i] - 1, 104857601) * qp(i, 2 * phi[n/i] - 1, 104857601) % 104857601, 104857599, 104857601)) %= 104857601;} cout << prod;
}