Problem Description

Lanqiao Company is located in the Cloud City and has $2025$ employees. Each employee has a unique ID from $1$ to $2025$. Every year, the company holds a grand party and invites some employees to improve team bonding.

In the company structure, for every employee with ID $x$, their direct boss has ID $2x$. To keep the party relaxed, the company sets a rule: if employee $x$ is invited to the party, then their direct boss $2x$ must not be invited. This rule comes from last year’s party, when an employee and their boss showed up at the same time and caused awkward “report-style chatting”, which ruined the fun atmosphere.

Now, your task is to compute how many invitation plans there are such that for any invited employee $x$, their direct boss $2x$ is not invited. Since the answer may be very large, you only need to output the result modulo $10^9 + 7$. An invitation plan means a choice of a set of employees to attend the party (the order of invitation does not matter) that satisfies the rule above. For example:

• Inviting $\{1, 3, 5, 7, 9\}$ is valid, because the bosses of employees $1, 3, 5, 7, 9$ are not invited.
• Inviting $\{1, 2\}$ is invalid, because employee $1$’s boss $2$ is invited.
• Inviting no one (the empty set) is also valid, because no employees are invited, so the rule is naturally satisfied.

Output Format

This is an output-only fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer in the range from $0$ to $10^9 + 6$. When submitting, only fill in this integer; any extra content will not be scored.

Hint

Translated by ChatGPT 5