Sum of super exponentiation $f(x,n)=x^{2^{1}}+x^{2^{2}}+x^{2^{3}}+...+x^{2^{n}}$
Example: $f(2,10)$ mod $1000000007$ = $180974681$
Calculate $\sum_{x=2}^{10^{7}} f(x,10^{18})$ mod $1000000007$.
We know that $a^{b^{c}}$ mod $p$ = $a^{b^{c} \hspace{0.5 mm} mod \hspace{1 mm} (p-1)}$ mod $p$.
So I tried to find the period of the sequence $2^n$ mod $1000000006$.
$\varphi(1000000006)=500000002$ is an integral multiple of this period. But I am stuck here. Any help please?
I verified that the period of the sequence $2^n$ mod $1000000006$ is indeed $500000002$.
 A: Hint: $1000000006=2\cdot500000003$. The smallest number $n$ such that $$2^n \equiv 1 \mod k$$
If $\gcd(n,k)=1$, is equal to $\lambda(k)$, the Carmichael function. For prime $p$, we have $\lambda(p)=\varphi(p)$. So
$$2^{500000002} \equiv 1 \mod 500000003$$
And $500000002$ is the smallest such number.
Alternatively, $ 500000002$ has only 4 prime factors, (2, 41, 41, 148721) so you can test all divisiors.
A: Partial answer: You are looking for (the remainder $\mod p$ of)
$$ \sum_{x=2}^{A}f(x,B)=\sum_{x=2}^{A}\sum_{y=1}^Bx^{2^y}=\sum_{y=1}^B\sum_{x=2}^{A}x^{2^y}.$$
Since $p\equiv 3\pmod 4$, squaring is a bijection $\mod p$. We conclude by induction on $y$ that
$$\sum_{x=k+1}^{k+p}x^{2^y}\equiv \sum_{x=k+1}^{k+p}x\equiv 0\pmod p. $$
Hence
$$ \sum_{x=2}^{A}x^{2^y}\equiv \sum_{x=2}^{A\bmod p}x^{2^y}= \sum_{x=2}^{49}x^{2^y}$$
and you are in fact looking for
$$\sum_{x=2}^{49}f(x,B).$$
A: Let $q=5000000003$ and $p=2q+1$
As $10^{18}=1999999992*(q-1)+16$, we have
$f(x,10^{18})=1999999992*(x^2+x^4+...+x^{2(q-1)})+(x^{2^{1}}+x^{2^{2}}+...+x^{2^{16}})$
Now we can use the fact that $2$ is a primitive root modulo $q$
$x^2+x^4+...+x^{2(q-1)}=x^2 \frac{x^{2(q-1)}-1}{x^2-1}\equiv -1$ mod $p$.
So we just have to compute $16*10^7$ values.
