Hi everyone!

I need some help with the problem 2147G - Modular Tetration. In the editorial there is this identity

$$$\sum_{x|\varphi(m), rad(x) | k} cnt(x) = \sum_{d_1| q_1^{\beta_1}, \ldots , d_t | q_t^{\beta_t}} \prod \varphi(d_i)$$$

Where $$$k$$$ is a square-free number with $$$gcd(k, m) = 1$$$ and $$$k | \varphi(m)$$$. $$$cnt(x)$$$ is the number of remainders $$$1 \le a \lt m$$$ for which $$$ord_m(a) = x$$$. $$$k = q_1 q_2 \ldots q_t$$$ and $$$\beta_i$$$ is the exponent of $$$q_i$$$ in $$$\varphi(m)$$$

It is some counting in 2 ways, as far as I understand. I tried to prove this for several days, now I am desperate to know the proof since the editorial mentions this as something obvious and the author of the problem doens't respond.