P15431 [Lanqiao Cup 2025 National Python B] Party Invitation Plans

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.

N/A

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.

Translated by ChatGPT 5