Problem Background

Corycle enjoys playing a turn-based combat game developed by miHoYo - "Honkai: Star Rail." In this galaxy, there exist entities known as "Star Gods" who create reality, erase stars, and leave their marks across countless "worlds." You will explore new civilizations, meet new companions, and embark on new adventures between the fantastical "worlds." All the answers you seek will be found among the stars.

Problem Description

In the game "Honkai: Star Rail," your team consists of four characters who take turns acting, and all characters share the same skill points for using their abilities. At the beginning of the battle, you receive $k$ skill points, with a maximum limit of 5 skill points. Each character can choose to perform a normal attack or use their ability when it's their turn. A normal attack adds one skill point to the team, and even when the skill points reach the maximum, a character can still perform a normal attack without recovering additional skill points. Using an ability consumes one skill point, and without any skill points, a character can only perform a normal attack and cannot use their ability.

Corycle wants to become a master of Star Rail, and for that, he needs to be thoroughly familiar with his team composition. Since characters have various professions and for ease of character classification, he categorizes the characters' action patterns into three types:

1. When the character acts, they will only perform a normal attack.
2. When the character acts, they will use their ability if they have at least 1 skill point; otherwise, they perform a normal attack.
3. No restrictions are placed on the character's actions.

Now, Corycle is starting a battle, and he wants to know how many different action plans are possible when the four characters in his team act a total of $n$ times. Two action plans are considered different if and only if there is at least one round where the characters' actions differ. Since the answer could be a very large number, please output the answer modulo $998244353$.

Input Format

The first line of input 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 a space.

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

Output Format

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

Sample Input and Output

Sample Input #1

12 1
2 3 2 1

Sample Output #1

1

Sample Input #2

8 5
2 1 1 3

Sample Output #2

4

见题面 Input 部分

见题面 Output 部分