Кішкентай N жақында MEX туралы білді. MEX (Minimum Excluded) массивте кездеспейтін ең кіші теріс емес бүтін санды білдіреді. Мысалы: $\operatorname{{MEX}}([3, 1, 0]) = 2$, $\operatorname{{MEX}}([2, 2, 1]) = 0$, $\operatorname{{MEX}}([0, 3, 1, 2]) = 4$. Кішкентай N ұзындығы $k$ болатын $[b_1, b_2, \dots, b_k]$ теріс емес бүтін сандар массиві үшін, егер $\operatorname{MEX}([b_1, b_2, \dots, b_k]) = k$ болса, онда $b$ массиві $k$-жақсы массив деп аталады деп анықтайды.

Оң бүтін сан $n$ берілген. $n$-жақсы $p_1, p_2, \dots, p_n$ массиві үшін Кішкентай N $f(p)$ функциясын келесі шарттарды қанағаттандыратын $(l, r)$ бүтін сандар жұптарының саны ретінде анықтайды:

• $1 \le l \le r \le n$;
• $p_l, \dots, p_r$ — $(r - l + 1)$-жақсы массив.

Кішкентай N келесі теореманы дәлелдеді: кез келген $n$-жақсы $p$ массиві үшін $1 \le f(p) \le n$ орындалады. Енді Кішкентай N сізден әрбір $i \in [1, n]$ үшін $f(p) = i$ болатын $n$-жақсы $p$ массивтерінің санын табуды сұрайды. Әрине, бұл сан өте үлкен болуы мүмкін, сондықтан нәтижені $998\,244\,353$ модулі бойынша шығару қажет.

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

Кіріс деректер бүтін сан $n$ ($1 \le n \le 10^5$) жазылған жалғыз жолдан тұрады.

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

$n$ бүтін саннан тұратын бір жолды шығарыңыз, мұндағы $i$-ші бүтін сан $f(p) = i$ шартын қанағаттандыратын $n$-жақсы $p$ массивтерінің санын $998\,244\,353$ модулі бойынша білдіреді.

Мысалдар

1-мысал кірісі

1

1-мысал шығысы

1

2-мысал кірісі

3

2-мысал шығысы

0 2 4

3-мысал кірісі

7

3-мысал шығысы

0 2312 1424 728 352 160 64

Ескертпе

$n = 3$ үшін алты $3$-жақсы массив бар екенін дәлелдеуге болады, олардың сәйкес функция мәндері:

$f([0, 1, 2]) = 3$, $f([0, 2, 1]) = 2$, $f([1, 0, 2]) = 3$, $f([1, 2, 0]) = 2$, $f([2, 0, 1]) = 3$, $f([2, 1, 0]) = 3$