This is easier than P4 imo

Let $k$ be the number of primes that divide $n$. Notice that if $p^l|a_i$ then for all $j\neq i$ we have $a_j^m\equiv 1$ (mod $p^l$) and $a_i^m\equiv 0$ (mod $p^l$). So the value of $k$ and set of primes amongst $a_i$ is enough to uniquely determine the sum. Pairing up cases we get an answer of $\frac{k}{2}\cdot 2^k=k2^{k-1}$.

Answer. $k\cdot 2^{k-1}$, where $k$ is the number of positive prime divisors of $n$. Official Solution. Let $p_1^{\alpha_1}\cdot\cdots p_k^{\alpha_k}$, with $p_1 < \cdots < p_k$, be the prime factorization of $n$, and for any positive integer $m$ we denote $\mathbb{Z}_m$ as the integers modulo $m$. Consider the mapping $\varphi: \mathbb{Z}_n\to \mathbb{Z}_{p_1^{\alpha_1}}\times \cdots \times \mathbb{Z}_{p_k^{\alpha_k}}$ such that \[ \varphi(\ell) = (\ell\pmod{p_1^{\alpha_1}}, \cdots, \ell\pmod{p_m^{\alpha_m}})\]Then by the Chinese Remainder Theorem (CRT), $\varphi$ is a bijection, so we will work on the $k$-tuples in $\mathbb{Z}_{p_1^{\alpha_1}}\times \cdots \times \mathbb{Z}_{p_k^{\alpha_k}}$ instead. In this system, we denote $(b_1, \cdots, b_k) + (b_1', \cdots, b_k') = (b_1+b_1', \cdots, b_k + b_k')$, and also denote $(b_1, \cdots, b_k) \equiv (b_1', \cdots, b_k')$ if $b_i\equiv b_i'\pmod{p_i^{\alpha_i}}$ for all $i=1, \cdots, k$ (which again by CRT is well-defined). Then the mapping $\varphi$ is additive, i.e. $\varphi(x + y) = \varphi(x) + \varphi(y)$. Denote $\textbf{1}_T$ as 1 if $T$ is true as 0 if $T$ is false. An initial observation is that for any number $x$, $\varphi(x^m) = (\textbf{1}_{p\nmid p_1}, \cdots, \textbf{1}_{p\nmid p_m})$. Indeed, if $p_i\nmid x$ then $x^m\equiv 1\pmod{p_i^{\alpha_i}}$ since $\phi(p_i^{\alpha_i}) = p_i^{\alpha_i - 1}(p_i - 1)\mid m$. Otherwise, if $p_i\mid x$, then $p_i^m\mid x^m$, and \[ m = \prod_{j=1}^k p_j^{\alpha_j-1}(p_j-1)\ge p_i^{\alpha_i-1}(p_i-1) \ge 2^{\alpha_i - 1}\ge \alpha_i\]and therefore $p_i^{\alpha_i}\mid x^m$, resulting in remainder 0 on the $i$-th coordinate. Now define $$ U = \left\{\varphi\left(\sum_{a_i\in T}a_i^m\right): T\text{ good}\right\}$$Denote, also, $U_{\ell}$ as the set of $k$-tuples $(b_1, \cdots, b_k)$ such that $\ell - 1\le b_i\le\ell$ for all $i=1, \cdots, k$ and at least $\ell$ of these numbers $b_i$ are $\ell - 1$. We claim that $U = \bigcup_{\ell=1}^{k} U_{\ell}$. For sufficiency, suppose for some $\ell\le n$, $(b_1, \cdots, b_k)\in U_{\ell}$, consider $I=\{i_1, \cdots, i_c\}\subseteq \{1, \cdots, k\}$ such that $b_i=\ell-1$ if and only if $i\in I$. Then $|I|=c\ge \ell$ and therefore we can choose, for example, $a_j=p_{i_j}$ for $j=1, \cdots, \ell-1$, and then $a_\ell = p_{i_\ell}\cdots p_{i_c}$. Conversely, suppose $\{a_i, \cdots, a_{\ell}\}$ is good. Suppose $b_{i, 1}, \cdots, b_{i, k}$ ($i=1, \cdots , \ell$)are such that \[ \varphi(\sum_{i=1}^{\ell} a_{i}^{m}) =\sum_{i=1}^{\ell}\varphi(a_i^m)=\sum_{i=1}^{\ell}(b_{i, 1}, \cdots, b_{i, k})\]Denote, also, $b_j = b_{1, j} + \cdots + b_{\ell, j}$, i.e. $\varphi(\sum_{i=1}^{\ell} a_{i}^{m}) = (b_1, \cdots, b_k)$. Then $b_{i,1}\in \{0, 1\}$, at least one of $b_{i,1}, \cdots, b_{i,k}$ is 0 for each $i=1, \cdots, \ell$ (since $\gcd(a_i, n) > 1$), and at most one of $b_{1,j}, \cdots, b_{\ell , j}$ is 0 (since $a_i, a_j$ cannot both share a prime divisor of $n$). This means there are a total of at least $\ell$ indices $b_{i'j'}$ that are 0, with $j'$ being pairwise different for these, and hence $(b_1, \cdots, b_k)\in U_{\ell}$ and $\ell\le k$. Now we are ready to count $|U|$. We first show that $U_1, U_2, \cdots, U_k$ are pairwise disjoint. Suppose that $(b_1, \cdots, b_k)\in U_{\ell}$and $(b_1', \cdots, b_k')\in U_{\ell'}$ for some $\ell, \ell'$ are such that $(b_1, \cdots, b_k)\equiv (b_1', \cdots, b_k')$. Since $n$ is odd, and $3\le p_1 < \cdots p_k$, we have $p_k \ge k + 2$. In addition, $b_i$'s, $b_i'$'s can be choosen (up to modulo $p_i^{\alpha_i}$) such that\[0\le \ell - 1\le b_k\le \ell\le k,\qquad 0\le \ell' - 1\le b_k'\le \ell'\le k.\]Thus we have $b_k = b_k'$, and so $|\ell - \ell'|\le 1$. If $\ell' = \ell + 1$, then $b_i\in \{\ell - 1, \ell\}$ and $b'_i\in \{\ell, \ell + 1\}$, and since $p_i \ge 3$ for all $i$, the only possibility is $b_i = b_i' = \ell$ for all $i$. However, this contradicts that each element in $U_{\ell}$ must have at least $\ell$ elements being $b_i$. In a similar way we can show that $(b_1, \cdots, b_k), (b_1', \cdots, b_k')\in U_{\ell}$ and $b_i\equiv b_i'\pmod{p_i^{\alpha_i}}$ implies that $b_i=b_i'$. This gives $|U_{\ell}| = \sum_{p=\ell}^k \binom{k}{p}$ for each $\ell$. Therefore, we may now count $S$ as $$\displaystyle |S_n| =|U| = \sum_{\ell=1}^k |U_{\ell}| = \sum_{\ell=1}^{k}\sum_{p=\ell}^k \binom{k}{p} =\sum_{p=1}^k (k-p)\binom{k}{p} =k\sum_{p=1}^{k-1}\binom{k-1}{p-1} =k\cdot 2^{k-1} $$as desired. Remark. The conclusion still holds if $4\mid n$, or $n = 2$. For $n > 2$ in the form $4k+2$, setting $p_1=2$ we have $(0, 1, \cdots, 1)=(2, 1, \cdots, 1)$, so it's simultaneously in both $U_1$ and $U_2$ (this is also the only example). In this case the answer is $k\cdot 2^{k-1} - 1$.