Let's Play with Functions

For every positive integer $n$, we first prove $f(n)=2^n$. The base case $f(1)=2$ holds. Moreover,

$$f(n+1)=f(n)f(1)=2f(n),$$

so the claim follows by induction.

For each query, we must compute $2^{n_i}\bmod M$, where $M=10^9+7$. Since is prime and coprime to , Fermat's little theorem gives

$$2^{M-1}\equiv1\pmod M.$$

Thus, if $e_i$ is the remainder of $n_i$ modulo $M-1=10^9+6$, then

$$2^{n_i}\equiv2^{e_i}\pmod M.$$

Because $n_i$ can be as large as $10^{200}$, read it as a decimal string. Process its digits $d_1,d_2,\cdots,d_k$ from left to right. Starting with , update

$$e\leftarrow(10e+d_j)\bmod(M-1).$$

Finally, compute $2^e\bmod M$ with binary exponentiation.

If query $i$ has $L_i$ decimal digits, the total time complexity is $O(\sum_{i=1}^Q L_i+Q\log M)$. The extra space, excluding the input string, is . The maximum input string length is .

Solution written by GPT6