A botanical greenhouse has n terrariums standing in a row, numbered 1 to n, and every terrarium's grow-light starts turned ON. The control panel has exactly four switches; each switch press instantly flips (ON becomes OFF, OFF becomes ON) a fixed subset of the lights, and every press is independent of what came before:
n lights.2, 4, 6, ...).1, 3, 5, ...).1, 4, 7, 10, ...).The keeper will press switches exactly m times in total, freely choosing which of the four switches to press at each of the m presses (the same switch may be pressed any number of times, including zero or many). Determine the number of distinct final lighting patterns (across all n lights) that are achievable after exactly m total presses.
A single line with two integers n and m separated by whitespace.
Print one integer: the number of distinct reachable lighting patterns after exactly m presses.
Example 1
Input
1 1
Expected
2
Explanation
With only 1 terrarium, switch 2 (even positions) never touches it, so it is effectively a do-nothing press; switches 1, 3, and 4 all flip the single light. With exactly 1 press you can either press switch 2 (light stays ON) or press switch 1/3/4 (light turns OFF), so both of the 2 possible patterns are reachable.
Example 2
Input
3 1
Expected
4
Explanation
With 3 terrariums, starting pattern is ON,ON,ON. A single press of switch 1 gives OFF,OFF,OFF; switch 2 gives ON,OFF,ON; switch 3 gives OFF,ON,OFF; switch 4 gives OFF,ON,ON (only position 1 is flipped since 4 > 3). These 4 single presses produce 4 distinct patterns, and no other pattern is reachable in exactly 1 press, so the answer is 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →