Оң бүтін сан $N$ және өлшемі $M$ болатын бүтін сандар жиыны $S = \{S_1, S_2, \dots, S_M\}$ берілген.
Әрбір $k = 0, 1, \dots, N - 3$ үшін келесі сұраққа жауап беріңіз.
Төбелері $1, 2, \dots, N$ сандарымен нөмірленген дұрыс $N$-бұрышты қарастырайық. Ешбір екі диагональ ұштарынан басқа жерде қиылыспайтындай етіп дәл $k$ диагональ жүргізіңіз. Нәтижесінде дұрыс $N$-бұрыш $k + 1$ көпбұрышқа бөлінеді. Осы пайда болған көпбұрыштардың қабырғалар санын $e_1, e_2, \dots, e_{k+1}$ деп белгілейік.
Егер $k$ диагональ жүргізу тәсілі келесі шартты қанағаттандырса, оны жақсы тәсіл деп атаймыз:
- $e_1, e_2, \dots, e_{k+1}$ сандарының барлығы $S$ жиынында жатады.
$k$ диагональ жүргізудің жақсы тәсілдер санын $998244353$ модулі бойынша есептеңіз.
Кіріс деректер
Кіріс деректер келесі форматта беріледі:
N M S1 S2 ... SM
- Барлық кіріс мәндері — бүтін сандар.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Шығыс деректер
$N - 2$ жол шығарыңыз. $i = 1, 2, \dots, N - 2$ үшін $i$-ші жолда $k = i - 1$ мәніне сәйкес келетін жауапты шығарыңыз.
Мысалдар
1-мысал кіріс
5 2 3 4
1-мысал шығыс
0 5 5
2-мысал кіріс
4 1 4
2-мысал шығыс
1 0
3-мысал кіріс
16 7 3 4 6 7 9 12 16
3-мысал шығыс
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Ескертпе
Бірінші мысалда $k = 0$ болғанда әрқашан $e_1 = 5$ болады. $5$ саны $S$ жиынына кірмейтіндіктен, жауап $0$ болады.
$k = 1$ болғанда әрқашан $\{e_1, e_2\} = \{3, 4\}$ болады және екі мән де $S$ жиынында бар. Дұрыс бесбұрышта бір диагональ жүргізудің $5$ тәсілі бар, сондықтан жауап $5$ болады.
$k = 2$ болғанда әрқашан $e_i = 3$ ($1 \le i \le 3$) болады. Дұрыс бесбұрышта өзара қиылыспайтын екі диагональ жүргізудің $5$ тәсілі бар, сондықтан жауап $5$ болады.