P10239 [yLCPC2024] G. Too Many Strings (系ぎて)

> It is not just that I feel unwilling, what even is this chart… > ——ReMiRiA > I am very happy to win the championship, but what is this chart? Will it really be included?? > ——yoshiki

Fusu really likes factoring natural numbers. For a given positive integer $n$, if $n = i \times j \times k$, where $i, j, k$ are positive integers, then the triple $(i, j, k)$ is called an excellent factorization of $n$. The triple $(i, j, k)$ is ordered. For example, for $2 = 1 \times 1 \times 2 = 1 \times 2 \times 1 = 2 \times 1 \times 1$, we consider $(1, 1, 2)$, $(1, 2, 1)$, and $(2, 1, 1)$ as three different excellent factorizations. Now, Fusu wants to ask: for $n = 1, 2, 3, \dots, N$, what is the total number of excellent factorizations of all $n$? Formally, let $f(n)$ be the number of excellent factorizations of $n$. You need to compute $\sum_{i = 1}^N f(i)$.

The input contains only one line with an integer $N$ ($1 \leq N \leq 10^{10}$).

Output one line with an integer representing the answer. Since the answer may be too large, you only need to output this value modulo $2^{64}$.

Translated by ChatGPT 5