Орын ауыстыру дегеніміз — $1$-ден $n$-ге дейінгі бүтін сандардан тұратын, барлық сандар дәл бір рет кездесетін ұзындығы $n$ болатын тізбек. Мысалы, $[1]$, $[3, 5, 2, 1, 4]$ және $[1, 3, 2]$ орын ауыстырулар болып табылады, ал $[2, 3, 2]$, $[4, 3, 1]$ және $[0]$ олай емес.

Сізге $N$ бүтін саннан тұратын $A_1, A_2, \dots, A_N$ массиві берілген. Әрбір бүтін сан $0$ немесе $1$-ге тең. Келесі шарттар орындалатындай өлшемі $N$ болатын $P$ орын ауыстыруларының санын табыңыз:

• $P_1 < P_2 > P_3 < P_4 \dots$
• Барлық ($1 \le i \le N$) үшін $A_{P_i} \equiv i \pmod 2$.

Мұндай орын ауыстырулар саны өте үлкен болуы мүмкін болғандықтан, жауапты $998244353$ модулі бойынша шығарыңыз.

Кіріс деректері

Бірінші жолда бір бүтін сан $N$ ($1 \le N \le 10^6$) берілген.

Екінші жолда бос орын арқылы бөлінген $N$ бүтін сан $A_i$ — массив элементтері берілген. $A_i \in \{0, 1\}$ екеніне кепілдік беріледі.

Шығыс деректері

Шарттарды қанағаттандыратын орын ауыстырулар санын $998244353$ модулі бойынша бір жолда шығарыңыз.

Мысалдар

Кіріс мысалы 1

2
1 0

Шығыс мысалы 1

1

Кіріс мысалы 2

1
0

Шығыс мысалы 2

0

Кіріс мысалы 3

7
1 1 0 1 0 1 0

Шығыс мысалы 3

8