String Erasing Game

Time limit1sMemory limit1024 MB

Summary

Given a string of 0, 1, and at most one ?, decide whether the first player wins the game of erasing end runs or filling in the ?.

Level: Medium6 of 10
Topics: String, Game theory, Greedy
Solved: No attempts yet

Problem

Junbeom and Myeongseop are playing a string erasing game.

The string erasing game uses a string made only of 0, 1, and ?. The string contains at most one ?. The two players take turns, choosing one of the following actions.

Erase one or more of the identical consecutive digits at the front of the string.
Erase one or more of the identical consecutive digits at the back of the string.
Change one ? in the string to 0 or 1.

Junbeom moves first. A player who has no possible action left loses. Assuming both players play optimally to win, determine which player wins.

Input

The first line contains the string $S$ used in the game. $S$ is a string of length at least $1$ and at most $1\,500$ made only of 0, 1, and ?, and at most one ? is given.

Output

If Junbeom wins, print 1. If Myeongseop wins, print 0.

Examples2

Example 1
Input
```
0
```
Expected output
```
1
```
Example 2
Input
```
?
```
Expected output
```
0
```