문자열 지우기

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

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

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

준범이가 먼저 시작한다. 더 이상 할 수 있는 행동이 없는 사람이 진다. 두 사람이 모두 이기려고 최선을 다할 때 누가 이기는지 구하라.

첫째 줄에 게임에 사용할 문자열 $S$가 주어진다. $S$는 0, 1, ?만으로 이루어진 길이 $1$ 이상 $1\,500$ 이하의 문자열이며, ?는 둘 이상 주어지지 않는다.

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