Background

TJOI2019 D1T3.

Source file name: queue.*.

Time limit: 4 s. Memory limit: 128 M.

Problem Description

Da Zhongfeng’s academy is going to organize students to visit a museum, and requires the students to line up in a single queue in the museum.

His classmates can be divided into four types: some like singing the most, some like dancing the most, some like rap the most, and some like basketball the most. If the students at positions $k$, $k + 1$, $k + 2$, $k + 3$ in the queue, in order, like singing the most, like dancing the most, like rap the most, and like basketball the most, then they will gather together to discuss Cai Xukun. Da Zhongfeng does not want this to happen, because it will make the queue look messy.

Da Zhongfeng wants to know how many ways there are to arrange the queue so that no students will gather together to discuss Cai Xukun. Two queues are considered different if and only if there exists at least one position where the students’ preferences are different. Since the number of valid queues may be very large, output it modulo $998244353$.

Input Format

The input contains only one line. The line contains $5$ integers. The first integer is $n$, the number of students going to visit the museum. The next four integers $a$, $b$, $c$, $d$ represent the number of students who like singing the most, like dancing the most, like rap the most, and like basketball the most, respectively. It is guaranteed that $a+b+c+d \ge n$.

Output Format

Output one integer, representing how many different student queues you can arrange such that there are no students gathering together to discuss Cai Xukun. Output the result modulo $998244353$.

4 4 3 2 1

174

996 208 221 132 442

442572391

Hint

For $20\%$ of the testdata, $n=a=b=c=d\le500$.

For $100\%$ of the testdata, $n \le 1000$, $a, b, c, d \le 500$.

Translated by ChatGPT 5