Alice noticed this trend in some contest problems where they add "flavor" to a pure mathematical statement by introducing some formal abstract arbitrary property and then binding it to an adjective that has absolutely nothing to do with that definition. These problems are usually then titled "adjective + mathematical object". For example, "beautiful numbers", "interesting sequences", and the classic "good colorings". As an aspiring problem setter, Alice wishes to partake in this tradition.

A $$$k$$$-jolly divisor of $$$n$$$ is some positive integer $$$d$$$ such that $$$n$$$ is divisible by $$$d$$$ and by $$$d^k$$$. For example, $$$4$$$ is a $$$3$$$-jolly divisor of $$$960$$$, since both $$$4$$$ and $$$4^3 = 64$$$ divide $$$960$$$. We can show that $$$4$$$ is the largest $$$3$$$-jolly divisor of $$$960$$$.

Given $$$N$$$ and $$$k$$$, find the sum of the largest $$$k$$$-jolly divisors of $$$n$$$ across all $$$n$$$ from $$$1$$$ to $$$N$$$.

Python users are advised to submit to PyPy for this problem.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq k \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & 1 \leq n \leq 10^3 \\ \hline 2 & \mathbf{30} & 1 \leq n \leq 10^5 \\ \hline 3 & \mathbf{30} & 1 \leq n \leq 10^6 \\ \hline 4 & \mathbf{10} & 1 \leq n \leq 5 \times 10^7 \\ \hline \end{array}\\

\end{align*}$$$$$$