We first find an expression for $s$. Let $x = n+a$, where $n$ is an integer and as large as possible. Then, the given equation becomes $(n+a)(na) + n + a = 4^{2023}$. We can rearrange this as a quadratic in $a$ to obtain $$na^2 + (n^2+1)a + (n-4^{2023}) = 0.$$Fix $n$, and, using the quadratic formula and simplifying the expression inside the radical, we find that $$a = \frac{-n^2-1 \pm \sqrt{(n^2-1)^2 + 4^{2024}n}}{2n}.$$Clearly, for any given $n$, there is at most one solution $a$, since the negative of the above solution for $a$ is negative for all positive $n$ (note $n\ne 0$), which is impossible. Thus, it remains to find all $n$ such that $$0 \le \frac{-n^2-1 + \sqrt{(n^2-1)^2 + 4^{2024}n}}{2n} < 1.$$ We deal with the lower bound first: our given solution for $a$ to be greater than or equal to $0$, we must have $$(n^2 + 1)^2 \le (n^2-1)^2 + 4^{2024}n.$$Bringing the $(n^2-1)^2$ term to the LHS and using difference of squares, it is easy to obtain that we must have $n\le 4^{2023}$. Now, we deal with the upper bound. For our expression for $a$ to be less than $1$, we must have $$(n^2-1)^2 + 4^{2024}n < (n+1)^4.$$Bringing the $(n^2-1)^2$ term to the RHS and factoring, we quickly obtain that $2^{2023} < n+1$. Hence, $n \ge 2^{2023}$. This means that $s = 4^{2023} - 2^{2023} + 1$. All we must find now is $s \pmod{1000}$. To do this, we first write $s = 2^{4046} - 2^{2023} + 1$. Now, we will simply find $s \pmod{125}$, since we already know $s \equiv 1 \pmod{8}$. By Euler, we know that $2^{100} \equiv 1 \pmod{125}$, so the matter reduces to finding $2^{46} - 2^{23} + 1 \pmod{125}$. Observe that $2^{20} \equiv 24^2 \equiv 76 \pmod{125}$. Thus, $2^{23} \equiv 76 \cdot 8 \equiv 108 \pmod{125}$. This means that $2^{46} \equiv 108^2 \equiv 17^2 \equiv 39 \pmod{125}$. Thus, $s\equiv 39 - 108 + 1 \equiv 57 \pmod{125}$. Finally, note that $57 \equiv 1 \pmod{8}$, which means that the answer is $\boxed{057}$.