Problem Background

TJOI2019 D1T3

Source file name: queue.*

Time limit: 4s Memory limit: 128M

Problem Description

Big Center's college is organizing a visit to a museum, requiring students to line up in a queue for the visit. The students can be categorized into four types: those who love singing, those who love dancing, those who love rap, and those who love basketball. If the students at positions $k$, $k + 1$, $k + 2$, and $k + 3$ in the queue are respectively those who love singing, dancing, rap, and basketball, they will gather to discuss Cai Xukun. Big Center does not want this to happen as it would make the queue look chaotic. He wants to know how many ways there are to arrange the students in a queue such that no students gather to discuss Cai Xukun. Two student queues are considered different if and only if there is at least one position where the students have different preferences. Since there may be many valid queues, the number of different queues should be taken modulo $998244353$.

Input Format

The input data consists of a single line with five integers. The first integer $n$ represents the number of students Big Center's college is organizing to visit the museum. The next four integers $a$, $b$, $c$, and $d$ represent the number of students who love singing, dancing, rap, and basketball, respectively. It is guaranteed that $a + b + c + d \ge n$.

Output Format

For each set of data, output a single integer representing the number of different student queues that can be arranged such that no students gather to discuss Cai Xukun. The result should be taken modulo $998244353$.

Sample Input and Output

Sample Input #1

4 4 3 2 1

Sample Output #1

174

Sample Input #2

996 208 221 132 442

Sample Output #2

442572391

Notes

For 20% of the data, $n = a = b = c = d \le 500$.

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

见题面 Input 部分

见题面 Output 部分