Problem description

Nie da się ukryć, że technologia rozwija się w zatrważającym tempie, a nawet krasnoludki idą z duchem czasu. Z tego też powodu postanowiły one połączyć swoje N domków siecią przewodową, używając do tego N − 1 połączeń.

Sieć w wiosce powstała w szczególny sposób: krasnoludki na początku wybrały pewną liczbę k ∈ [1,N−1], po czym połączyły pewien domek o numerze z przedziału [1,k] z pewnym domkiem z przedziału [k+1,N]. Następnie, stosując tę samą zasadę, połączyły ze sobą domki od 1 do k oraz w ten sam sposób domki od k + 1 do N.

Teraz krasnoludkom zależy na tym, żeby odtworzyć połączenia w sieci. Niestety, jest to bardzo trudne zadanie, gdyż jedyną rzeczą zapisaną w dokumentacji jest schemat, według którego powstawała sieć. Schemat ma następującą postać:

• wyrażenie 1 oznacza domek (o numerze równym liczbie znaków 1, które dotychczas wystąpiły w schemacie, więc kolejne znaki 1 oznaczają domki o kolejnych numerach 1, 2, …, N),
• wyrażenie ( E₁ E₂ ), gdzie E₁ i E₂ są poprawnymi wyrażeniami, oznacza stworzenie sieci dla kolejnych domków według schematu E₁, następnie tak samo dla E₂, po czym połączenie pewnego domku z E₁ z pewnym domkiem z E₂.

Taki schemat ogranicza liczbę możliwych zestawów połączeń, ale nie jest jednoznaczny. Przykładowo, wyrażenie (1(11)) może opisywać dwa różne zestawy połączeń, pokazane poniżej.

Wewnętrzne wyrażenie (11) tworzy podsieć z dwóch domków o numerach 2 i 3 oraz łączy je krawędzią, na rysunkach przedstawiono ją linią kropkowaną. Zewnętrzne wyrażenie (1(11)) dokłada domek 1 i łączy go z wybranym domkiem podsieci {2, 3}, co przedstawiono linią przerywaną — w Wariancie 1 wybrano domek 2, a w Wariancie 2 domek 3. W ten sposób z wyrażenia (1(11)) można otrzymać dwa różne zestawy połączeń.

Jak łatwo zauważyć, liczba możliwych zestawów połączeń wynikających z jednego schematu może być bardzo duża. Szczęśliwie okazało się, że jeden z krasnoludków zauważył w dokumentacji drugi schemat, stworzony według tych samych zasad, opisujący tę samą sieć. Niestety, nawet dwa różne schematy mogą okazać się niewystarczające do jednoznacznego odtworzenia sieci.

Czy jesteś w stanie pomóc krasnoludkom policzyć, ile jest możliwych zestawów połączeń spełniających oba schematy?

Wejście

Na wejściu znajdują się dwa wiersze, a każdy z nich zawiera jeden opis schematu powstawania sieci, według podanych wyżej zasad.

Oba schematy są poprawne i mają tę samą długość, którą oznaczymy przez L.

Wyjście

W pierwszym (jedynym) wierszu wyjścia wypisz jedną liczbę całkowitą, oznaczającą liczbę możliwych zestawów połączeń, które można uzyskać z obu schematów. Ponieważ krasnoludki gubią się w dużych liczbach, wynik wypisz modulo 998 244 353.

Ograniczenia

1 ≤ L ≤ 700 000.

Przykłady

((1(11))1)
((11)(11))

1

(1(11))
(1(11))

2

(((11)(11))((11)1))
((1(11))(1(1(11))))

3

((11)(((1(11))1)((11)1)))
(1(((11)((11)(11)))(11)))

4