트리 생성기

입력으로 두 개의 식이 주어진다. 각 식은 트리 하나를 생성하는 절차를 나타낸다. 이 절차에는 무작위성이 있어서 실행할 때마다 서로 다른 트리가 만들어질 수 있다. 두 식 모두에서 생성될 수 있는 트리의 개수를 세시오.

식의 문법은 다음과 같다.

$E$ ::= ‘1’ | ‘(’ $E$ $E$ ‘)’

식으로부터 트리를 생성하는 절차는 다음과 같다.

• 식 1은 번호 $1$이 붙은 정점 하나로 이루어진 트리를 생성한다.
• 두 식 $E_1$, $E_2$에 대해 식 ($E_1E_2$)는 다음과 같이 트리를 생성한다.
  • $E_1$로부터 정점이 $n_1$개인 트리 $T_1$을, $E_2$로부터 정점이 $n_2$개인 트리 $T_2$를 생성한다.
  • $T_2$의 모든 정점 번호에 $n_1$을 더한다.
  • $T_1$의 정점 하나와 $T_2$의 정점 하나를 무작위로 고른다. 두 정점을 잇는 간선을 추가하면 번호가 $1$부터 $(n_1 + n_2)$까지인 트리 하나가 된다. 이것이 ($E_1E_2$)가 생성한 트리이다.

예를 들어 식 (11)이 생성할 수 있는 트리는 그림 D.1의 가장 왼쪽 트리뿐이다. 식 (1(11))은 나머지 두 트리를 생성할 수 있다.

그림 D.1. 두 식 (11)과 (1(11))로부터 생성되는 트리

같은 트리가 서로 다른 식에서 생성될 수도 있다. 가운데 트리는 ((11)1)에서도 생성될 수 있다.

길이가 같은 두 식이 주어질 때, 두 식 모두에서 생성될 수 있는 트리의 개수를 구하시오. 두 식에서 생성되는 트리의 정점 개수는 항상 같다. 두 트리는 어떤 두 번호 $i$, $j$에 대해 정점 $i$와 $j$가 한 트리에서는 간선으로 이어져 있고 다른 트리에서는 그렇지 않으면 서로 다른 트리이다.

입력은 두 줄로 이루어진다. 각 줄에는 식 문자열이 하나씩 주어진다. 두 문자열의 길이는 같으며, $1$ 이상 $7 \times 10^5$ 이하이다. 두 문자열 모두 위의 문법을 따른다.

두 식 모두에서 생성될 수 있는 트리의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

입력 예제 1에서 두 식이 생성할 수 있는 트리는 그림 D.2와 같다. 위쪽 여섯 개 트리는 첫 번째 식에서, 아래쪽 네 개 트리는 두 번째 식에서 생성된다. 각 행의 가장 왼쪽 트리만 두 식 모두에서 생성될 수 있다.

그림 D.2. 입력 예제 1의 설명