#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

using u128 = __uint128_t;
using u64 = uint64_t;

// 计算a*b mod m，使用快速乘法防止溢出
u128 mul_mod(u128 a, u128 b, u128 m) {
    u128 res = 0;
    while (b > 0) {
        if (b & 1) res = (res + a) % m;
        a = (a * 2) % m;
        b >>= 1;
    }
    return res;
}

// 计算a^b mod m，快速幂
u128 pow_mod(u128 a, u128 b, u128 m) {
    u128 res = 1;
    while (b > 0) {
        if (b & 1) res = mul_mod(res, a, m);
        a = mul_mod(a, a, m);
        b >>= 1;
    }
    return res;
}

// 计算n的欧拉函数值phi(n)
u128 euler_phi(u128 n) {
    u128 result = n;
    for (u128 i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

// 计算n的所有因数
vector<u128> get_divisors(u128 n) {
    vector<u128> divisors;
    for (u128 i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i)
                divisors.push_back(n / i);
        }
    }
    return divisors;
}

// 计算结果的最后120位
string solve(u128 n) {
    const u128 MOD = 1e120;
    vector<u128> divisors = get_divisors(n);
    u128 sum = 0;

    // 遍历n的所有因数d，计算每个因数对应的项并累加
    for (u128 d : divisors) {
        // 计算phi(n/d)，其中phi是欧拉函数
        u128 phi = euler_phi(n / d);
        // 计算17^d mod 1e120
        u128 term = pow_mod(17, d, MOD);
        // 计算term * phi mod 1e120
        term = mul_mod(term, phi, MOD);
        // 累加到总和中并取模
        sum = (sum + term) % MOD;
    }

    // 计算n在模1e120下的逆元
    // 由于n是奇数，与1e120互质，可以使用费马小定理计算逆元
    u128 inv_n = pow_mod(n, MOD - 2, MOD);
    // 计算最终结果：总和乘以n的逆元并取模
    u128 result = mul_mod(sum, inv_n, MOD);

    // 将结果转换为字符串表示，并补零到120位
    string res_str = "";
    u128 temp = result;
    // 逐位构建结果字符串
    while (temp > 0) {
        res_str = to_string(temp % 10) + res_str;
        temp /= 10;
    }
    // 确保结果字符串长度为120，不足则在前面补零
    while (res_str.length() < 120) {
        res_str = "0" + res_str;
    }
    return res_str;
}

int main() {
    u128 n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}