Factorial like product I am trying to solve http://www.javaist.com/rosecode/problem-519-Factorial-like-Product-askyear-2018
Restating the problem:
$$R(p,k)=\prod_{i=1}^{p-1}(i^k+1) \hspace{2 mm} \text{mod}\hspace{2 mm} p$$
$$S(P,k)=\sum_{3\le p\le P}R(p,k)$$
I need to calculate $R(P,k)$ for $P=10^{10}$ and $k=20181026$
For odd $k$, $R(p,k)$ is $0$. For a fixed prime $p$, $R(p,k)$ is periodic with period $p$. And also $R(p,p-1)=1$.
I am unable to proceed further. Any help will be appreciated.
 A: Notice $k = 2 \cdot 2069 \cdot 4877 = 2 \cdot k'$.
Fix an odd prime $p$, and let $d = (p-1,k')$, so that $k' \equiv dx \pmod{p-1}$. Since $d$ is the gcd of these two numbers, we have $(x,p-1) = 1$, and thus multiplying by $x$ just permutes the set $\{0,...,p-2\} \bmod{p-1}$, meaning, that for any primitive root $g \bmod{p}$,
$$
R(p,k) \equiv \prod_{i=1}^{p-1}(i^{2k'}+1) \equiv \prod_{r=0}^{p-2} (g^{2rk'}+1) \equiv \prod_{r=0}^{p-2}(g^{2drx}+1) \equiv \prod_{r=0}^{p-2}(g^{2dr}+1) \equiv
\left( \prod_{r=0}^{\frac{p-1}{2d}-1} (g^{2dr}+1) \right)^{2d} \pmod{p}
$$
With the last equivalence since $g^{2dr} = g^{2dr + (p-1)} = g^{2d \left( r + \frac{p-1}{2d} \right)}$.
Note since $p \equiv 1 \pmod{4}$ iff $-1$ is a quadratic residue $\bmod{p}$, we have  $R(p,k) = 0$ for all such $p$. Therefore, let $p \equiv 3 \pmod{4}$, where $-1$ is a nonresidue. Expand the inner product for $R(p,k)$ into elementary symmetric polynomials, $e_n(X)$.
Considering the power sums, we let $X = \left\{1,g^{2d},g^{4d},...,g^{2d\left(\frac{p-1}{2d} - 1\right)}\right\}$, and have, for $n \in \left\{1,...,\frac{p-1}{2d}-1 \right\}$:
$$
p_{n}(X)=\sum_{r=0}^{\frac{p-1}{2d}-1} g^{2dnr} = \frac{g^{2dn\left(\frac{p-1}{2d} \right)}-1}{g^{2dn}-1}=\frac{g^{n(p-1)}-1}{g^{2dn}-1}
$$
As $2d \mid p-1$, we have $p \ge 2d+1$. For $p>2d+1$, since $2dn \le p-(2d+1)$, this implies $p-1 \nmid 2dn$, so we have $g^{2dn}-1 \not\equiv 0 \pmod{p}$ while $g^{n(p-1)}-1 \equiv 0 \pmod{p}$, meaning $p_n(X) \equiv 0 \pmod{p}$. For $p = 2d+1$, this sum is the empty sum, so is trivially $0$.
Now by Newton's Identities, we have, $ne_n(X) = \sum_{i=1}^n (-1)^{i-1}e_{n-i}(X) p_i(X)$, so that $e_n(X) \equiv 0 \pmod{p}$ for all $n \in \left\{1,...,\frac{p-1}{2d} -1 \right\}$. This means that:
$$
R(p,k) \equiv \left( \left(\prod_{r=0}^{\frac{p-1}{2d}-1} g^{2dr}\right) +1\right)^{2d} \equiv \left(g^{2d\left(1+2+\ldots+\left(\frac{p-1}{2d}-1 \right)\right)} +1\right)^{2d} \equiv \left(g^{(p-1)\left(\frac{p-(2d+1)}{4d}\right)} + 1 \right)^{2d} \pmod{p}
$$
Since $p \equiv 3 \pmod{4}$ and $d$ is odd, we have $p-(1+2d) \equiv 3-1-2 \equiv 0 \pmod{4}$. Therefore $\frac{p-(2d+1)}{4d}$ is integral, and thus $R(p,k) \equiv 2^{2d} \pmod{p}$. Note this same argument works as long as $k'$ is odd, and for any $P$. For odd $k$, as you already noted, the sum is $0$.
