Problem 1538

1. Understanding the Problem:
We need to find the number of ordered 2011-tuples of positive integers $(a_1, a_2, \ldots, a_{2011})$ such that there exists a polynomial $f$ of degree 4019 satisfying:
- $f(n)$ is an integer for every integer $n$,
- $2011^2 \mid f(i) - a_i$ for $i = 1, 2, \ldots, 2011$,
- $2011^2 \mid f(n + 2011) - f(n)$ for every integer $n$.

2. Polynomial Properties:
- Since $f(n)$ is an integer for every integer $n$, $f$ must be a polynomial with integer coefficients.
- The condition $2011^2 \mid f(i) - a_i$ implies that $f(i) \equiv a_i \pmod{2011^2}$.
- The condition $2011^2 \mid f(n + 2011) - f(n)$ implies that $f(n + 2011) \equiv f(n) \pmod{2011^2}$.

3. **Analyzing the Polynomial $f$:**
- The condition $f(n + 2011) \equiv f(n) \pmod{2011^2}$ suggests that $f(x)$ is periodic with period 2011 modulo $2011^2$.
- This periodicity implies that $f(x)$ can be written in a form that reflects this periodicity. Specifically, $f(x)$ can be expressed as $f(x) = g(x) + 2011^2 h(x)$, where $g(x)$ is a polynomial of degree at most 4019 and $h(x)$ is some polynomial.

4. Counting the Number of Valid Polynomials:
- To satisfy $2011^2 \mid f(n + 2011) - f(n)$, the polynomial $f(x)$ must be such that $f(x + 2011) - f(x)$ is divisible by $2011^2$.
- This implies that the coefficients of $f(x)$ must be chosen such that the difference $f(x + 2011) - f(x)$ is zero modulo $2011^2$.

5. Using Polynomial Properties:
- Given $f(x) = a_{4019} x^{4019} + a_{4018} x^{4018} + \cdots + a_1 x + a_0$, the condition $f(x + 2011) \equiv f(x) \pmod{2011^2}$ must hold.
- This implies that each coefficient $a_i$ must be chosen such that the polynomial remains invariant under the transformation $x \to x + 2011$ modulo $2011^2$.

6. Counting the Number of Solutions:
- The number of such polynomials $f(x)$ modulo $2011^2$ is determined by the number of ways to choose the coefficients $a_i$ such that the periodicity condition is satisfied.
- Since each $a_i$ can take on $2011^2$ different values, and there are 4020 coefficients (from $a_0$ to $a_{4019}$), the total number of such polynomials is $(2011^2)^{4020}$.

7. Finding the Remainder:
- We need to find the remainder when the number of such polynomials is divided by 1000.
- $(2011^2)^{4020} \equiv (2011^2 \mod 1000)^{4020} \pmod{1000}$.
- $2011 \equiv 11 \pmod{1000}$, so $2011^2 \equiv 11^2 = 121 \pmod{1000}$.
- Therefore, $(2011^2)^{4020} \equiv 121^{4020} \pmod{1000}$.

8. Simplifying the Exponentiation:
- We need to compute $121^{4020} \mod 1000$.
- Using Euler's theorem, since $\phi(1000) = 400$, we have $121^{400} \equiv 1 \pmod{1000}$.
- Thus, $121^{4020} = (121^{400})^{10} \cdot 121^{20} \equiv 1^{10} \cdot 121^{20} \equiv 121^{20} \pmod{1000}$.

9. Final Calculation:
- We need to compute $121^{20} \mod 1000$.
- Using repeated squaring:
- $121^2 = 14641 \equiv 641 \pmod{1000}$,
- $641^2 = 410881 \equiv 881 \pmod{1000}$,
- $881^2 = 776161 \equiv 161 \pmod{1000}$,
- $161^2 = 25921 \equiv 921 \pmod{1000}$,
- $921^2 = 848241 \equiv 241 \pmod{1000}$,
- $241^2 = 58081 \equiv 81 \pmod{1000}$,
- $81^2 = 6561 \equiv 561 \pmod{1000}$,
- $561^2 = 314721 \equiv 721 \pmod{1000}$,
- $721^2 = 519841 \equiv 841 \pmod{1000}$,
- $841^2 = 707281 \equiv 281 \pmod{1000}$.

10. Conclusion:
- Therefore, $121^{20} \equiv 281 \pmod{1000}$.

The final answer is $\boxed{281}$.