Problem Description

By the pier where the tide sounds, the signal engineer Xiao Lan is responsible for maintaining a system of $2025$ signal lights. These lights are arranged in a line. Each light can be on or off, so there are $2^{2025}$ possible initial configurations.

To test the stability of the system, Xiao Lan designs an experiment: he chooses one initial configuration, then performs $2026$ independent state-switch operations—that is, flipping the state of some lights (on becomes off, off becomes on). Specifically:

• Operation 1: do not switch any light, keeping the initial state unchanged.
• Operation 2: switch the state of the leftmost 1 light.
• Operation 3: switch the state of the leftmost 2 lights.
• $\cdots$
• Operation 2025: switch the state of the leftmost 2024 lights.
• Operation 2026: switch the state of all lights.

After each operation, Xiao Lan records the number of lights that are on, then restores the lights to the chosen initial configuration before performing the next operation.

Xiao Lan finds that for some special initial configurations, among the numbers of lights that are on recorded in these $2026$ operations, there are only three distinct values. That is, the number of lights that are on after each operation only changes among three values, and no fourth distinct value appears.

Now Xiao Lan wants to know: among the $2^{2025}$ possible initial configurations, how many initial configurations make the recorded numbers of lights that are on in these $2026$ operations have exactly three distinct values? Please help him compute this number. Since the answer may be very large, you only need to output it modulo $10^9 + 7$.

Output Format

This is an output-only fill-in-the-blank problem. You only need to submit the result after calculating it. The result of this problem is an integer. When submitting the answer, only fill in this integer; any extra content will result in no score.

Hint

Translated by ChatGPT 5