Background

Corycle likes playing a turn-based battle game independently developed by miHoYo—Honkai: Star Rail. In this galaxy, there exist beings called “Aeons”. They shape reality and erase stars, leaving their traces across countless “worlds”. You will explore new civilizations, meet new companions, and start new adventures between countless strange and dazzling “worlds”. Everything you want to know can be found among the stars.

Problem Description

In the game Honkai: Star Rail, your team has four characters who take turns to act. All characters share “Skill Points” used to cast skills. When the battle starts, you get $k$ Skill Points, and the maximum number of Skill Points is $5$. Each time a character acts, they can choose to perform a normal attack or cast a skill. A normal attack increases the team’s Skill Points by $1$. When Skill Points have reached the maximum, you can still perform a normal attack, but it will not restore Skill Points. Casting a skill costs $1$ Skill Point. When there are no Skill Points, you can only perform a normal attack and cannot cast a skill.

Corycle wants to become a master of Star Rail, so he needs to fully understand his team. Since characters can have different roles, and to make it easier to classify their behavior, he divides each character’s action pattern into three types:

1. When the character acts, they will only perform a normal attack.

2. When the character acts, if there is at least $1$ Skill Point, they will definitely cast a skill; otherwise, they perform a normal attack.

3. There is no restriction on the character’s action.

Now Corycle starts a battle. He wants to know: when the four characters in the team take a total of $n$ actions, how many different action plans are possible? We say two action plans are different if and only if there exists at least one turn in which the character’s behavior is different between the two plans. The answer may be very large, so output it modulo $998244353$.

Input Format

The first line contains two positive integers $n$ and $k$ ($1\le n\le 1\times 10^{18},0\le k\le 5$), representing the total number of actions and the initial number of Skill Points, separated by spaces.

The second line contains four positive integers $a_1,a_2,a_3,a_4$ separated by spaces ($1 \le a_1,a_2,a_3,a_4 \le 3$), representing the action pattern types of the four characters.

Output Format

Output a single integer, representing the number of different action plans.

12 1
2 3 2 1

1

8 5
2 1 1 3

4

Hint

Translated by ChatGPT 5