키프로스의 인어

매년 여름 Stelinuța는 11일 동안 열리는 프로그래밍 캠프에 참가하러 키프로스에 간다. 그곳에 머무는 동안에는 바다에서 수영하고 스노클링하는 것을 즐긴다.

어느 날 스노클링을 하던 그녀는 아주 흥미로운 진주 목걸이를 발견했다. 진주가 달린 직선형(고리 모양이 아닌) 실이었다. 원래 모든 진주는 검은색이거나 흰색이었다. 하지만 일부 진주는 손상이 심해서 원래 색을 구별할 수 없었다.

이때 Stelinuța에게 아이디어가 떠올랐다. 목걸이에서 색이 같은 인접한 진주 두 개를 제거할 수 있다고 하자. 이 연산을 몇 번이든 적용해서 빈 목걸이만 남길 수 있도록 하는, 원래 목걸이의 서로 다른 색 배열은 몇 가지인가? 답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구하면 된다.

첫 줄에 Stelinuța가 발견한 목걸이를 나타내는 1, 0, ?로 이루어진 문자열이 주어진다. 각 진주는 다음과 같이 나타낸다.

• 1: 검은색 진주
• 0: 흰색 진주
• ?: 원래 색을 알 수 없는 진주

문자열의 길이는 1 이상 $2 \cdot 10^{5}$ 이하이다.

서로 다른 목걸이 모양의 수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

입력 예에서 가능한 목걸이는 011110 하나뿐이다. 11을 두 번 제거한 뒤 남은 00을 제거하면 빈 목걸이가 된다. 나머지 모든 경우에는 같은 색의 인접한 진주를 반복해서 제거하여 진주를 모두 없앨 방법이 없다.