31948번 - 문자열 지우기

문제

준범이와 명섭이가 문자열 지우기 게임을 하고 있다.

문자열 지우기 게임은 0, 1, ? 만으로 이루어진 문자열을 사용하는 게임이다. 문자열에 ?는 최대 하나 존재한다. 두 명이 다음 중 한 가지 행동을 번갈아 진행한다.

• 문자열 가장 앞의 연속된 같은 숫자 중 1ドル$개 이상을 지운다.
• 문자열 가장 뒤의 연속된 같은 숫자 중 1ドル$개 이상을 지운다.
• 문자열에 존재하는 ? 하나를 0 또는 1로 바꾼다.

준범이부터 문자열 지우기 게임을 시작한다. 더 이상 할 수 있는 행동이 없는 경우 패배한다. 준범이와 명섭이 모두 이기기 위해 최선을 다할 때 둘 중 누가 이기게 되는지 구해보자.

입력

첫째 줄에 문자열 지우기 게임에 사용할 문자열 $S$가 주어진다.

$S$는 0, 1, ? 만으로 이루어진 길이 1ドル$ 이상 1ドル,500円$ 이하의 문자열이고 ?는 둘 이상 주어지지 않는다.

출력

준범이가 이기게 되면 1, 명섭이가 이기게 되면 0을 출력한다.

제한

힌트