수열 연구자인 JAG 교수는 새로운 수식 언어를 개발하고 있습니다. 정수 $N$과 + 및 |로 이루어진 문자열 $O = O_1 O_2 \cdots O_{N-1}$이 주어집니다. 이 문제 전체에서 원소가 $a_1, a_2, \ldots, a_k$인 수열은 $[a_1, a_2, \ldots, a_k]$로 표기합니다.

다음 수식을 생각해 봅시다.

$$[1]\ O_1\ [2]\ O_2\ \ldots\ O_{N-1}\ [N]$$

여기서 $O_i$는 입력 문자열 $O$의 $i$번째 문자이며, $[i]$와 $[i + 1]$ 사이의 연산자로 사용됩니다.

연산자 우선순위가 정의되어 있지 않으므로, 피연산자와 연산자의 순서를 바꾸지 않고 이 수식에 괄호를 완전히 치는 모든 가능한 방법을 고려합니다. 이러한 방식으로 얻어지는 각 수식을 유효한 수식이라고 부릅니다.

각 수식 $Z$에 대해, $Z$가 나타내는 수열들의 집합을 $S(Z)$라 합시다. 집합 $S(Z)$는 다음과 같이 재귀적으로 정의됩니다.

• 만약 $Z$가 어떤 $i$ ($1 \le i \le N$)에 대해 [i] 형태라면, $S(Z)$는 원소가 하나인 수열 $[i]$만으로 구성됩니다.
• 만약 $Z$가 (X + Y) 형태라면 (여기서 $X$와 $Y$는 각각 왼쪽과 오른쪽 부분 수식), $S(Z)$는 $S(X)$에 속한 수열과 $S(Y)$에 속한 수열을 이어 붙여서 얻을 수 있는 모든 수열로 구성됩니다. 예를 들어, $S(X)$가 $[1, 3]$을 포함하고 $S(Y)$가 $[2, 4]$를 포함한다면, $S(Z)$는 $[1, 3, 2, 4]$를 포함합니다.
• 만약 $Z$가 (X | Y) 형태라면 (여기서 $X$와 $Y$는 각각 왼쪽과 오른쪽 부분 수식), $S(Z) = S(X) \cup S(Y)$입니다.

서로 다른 유효한 수식이 같은 수열을 나타낼 수도 있습니다. 적어도 하나의 유효한 수식에 의해 표현되는 서로 다른 수열의 개수를 구하세요. 답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력합니다.

입력

입력은 다음과 같은 형식의 단일 테스트 케이스로 이루어져 있습니다.

$$\begin{aligned} &N \\ &O \end{aligned}$$

첫째 줄에 정수 $N$ ($2 \le N \le 10^6$)이 주어집니다. 둘째 줄에 +와 |로 이루어진 문자열 $O$ ($|O| = N - 1$)가 주어집니다.

출력

표현될 수 있는 서로 다른 수열의 개수를 $998\,244\,353$으로 나눈 나머지를 출력합니다.

예제

입력 1

4
+|+

출력 1

4

입력 2

7
||+|||

출력 2

17

입력 3

17
+|||+|+++||||+|+

출력 3

1774

참고

첫 번째 예제에서 수식은 [1]+[2]|[3]+[4]입니다.

괄호를 추가하여 다음과 같이 다섯 개의 유효한 수식을 얻을 수 있습니다.

• ((([1]+[2])|[3])+[4])
• (([1]+[2])|([3]+[4]))
• (([1]+([2]|[3]))+[4])
• ([1]+(([2]|[3])+[4]))
• ([1]+([2]|([3]+[4])))

다음 네 개의 서로 다른 수열이 이 유효한 수식들 중 적어도 하나에 의해 표현됩니다.

• $[1, 2]$
• $[1, 2, 4]$
• $[1, 3, 4]$
• $[3, 4]$

따라서 답은 $4$입니다.