Вам надано непорожній рядок \(S\), що складається з (, ) і ?. Існує \(2^x\) способів отримати новий рядок, замінивши кожен ? у \(S\) на ( і ), де \(x\) — кількість входжень ? у \(S\). Серед них знайдіть число за модулем 998244353 способів, які дають рядок дужок.

Рядок називається рядком дужок, якщо виконується одна з наступних умов.

• Це порожній рядок.
• Це конкатенація (, A та ) для деякого рядка дужок A.
• Це конкатенація A та B для деяких непорожніх рядків дужок A та B.

Обмеження

• \(S\) є непорожнім рядком довжини щонайбільше 3000, що складається з (, ) і ?.

Формат вхідних даних

Вхідний потік містить \(S\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

(???(?

Приклад вихідних даних

2

Заміна \(S\) на ()()() або (())() дає рядок дужок. Інші заміни не дають рядка круглих дужок, тому виводимо 2.

Приклад вхідних даних

)))))

Приклад вихідних даних

0

Приклад вхідних даних

??????????????(????????(??????)?????????(?(??)

Приклад вихідних даних

603032273