Optimal Coin Game Winner

You are given a game with n coins. Two players take turns removing coins. Under optimal play, the outcome of the game is fully determined by the number of coins. In fact, it can be proved that if

\( n \equiv 0 \pmod{4} \),

the second player has a winning strategy and will win the game; otherwise, the first player can force a win. Your task is to determine the guaranteed winner given the number of coins \( n \).

Input Formula: The winning condition is given by the formula: \( Winner = \begin{cases} \text{Player 2} & \text{if } n \equiv 0 \pmod{4} \\ \text{Player 1} & \text{otherwise} \end{cases} \)

inputFormat

The input consists of a single line containing one integer \( n \) (1 \( \leq n \leq 10^9 \)), which represents the number of coins.

outputFormat

Output a single line with either "Player 1" or "Player 2" indicating the winner when both players play optimally.

1

Player 1