AT_kupc2019_k.One or All

アンジェ喜欢用变量玩耍。

今天她准备了 $3$ 个变量 $x,~y,~z$，打算用它们来玩。这三个变量初始值均为 $0$。

アンジェ打算对这些变量进行 $n$ 次操作，每次可以选择以下任意一种操作：

• 选择一个变量，将其值加 $1$ 或减 $1$。
• 将三个变量的值都加 $1$ 或都减 $1$。

经过 $n$ 次操作后，如果 $x,~y,~z$ 分别除以 $m$ 的余数为 $p,~q,~r$，アンジェ就会感到满意。

アンジェ对有多少种能让她满意的操作序列感兴趣。请帮她计算这样的操作序列的种数，并输出对 $998244353$ 取模的结果。

这里，若存在某个整数 $i\ (1\leq i\leq n)$，使得第 $i$ 次操作后至少有一个变量的值不同，则认为两个操作序列是不同的。

输入以如下格式从标准输入读入：

$n$ $m$ $p$ $q$ $r$

输出能让アンジェ满意的操作序列的种数，对 $998244353$ 取模。

限制条件

• 所有输入均为整数。
• $1\leq n\leq 10^6$
• $1\leq m\leq 10^6$
• $0\leq p,\ q,\ r < m$

样例解释 1

在一次操作中，无法只让某一个变量的值加 $1$，而让剩下的两个变量的值减 $1$。

样例解释 2

首先，将三个变量的值都减 $1$。接着只将 $x$ 的值减 $1$，此时 $x$ 的值为 $-2$，$y$ 和 $z$ 的值为 $-1$。它们分别除以 $3$ 的余数为 $1,~2,~2$，因此アンジェ对这个操作序列感到满意。能让アンジェ满意的操作序列有 $2$ 种，包括这个操作序列。

由 ChatGPT 4.1 翻译