QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 4903. 细菌

Statistics

科学家们搭建了一个巨大的细菌培养箱。这个培养箱是一个巨大的长方体,其长、宽、高分别为 $n,m,k$,被划分为 $n×m×k$ 个 $1×1×1$ 的小格。我们建立一个三维空间直角坐标系,用 $(x,y,z)(1≤x≤n,1≤y≤m,1≤z≤k)$ 来描述一个小格的位置。

在实验开始的时候,每个小格都恰有 $1$ 个细菌。接下来每天,所有细菌都会分裂。设一个在 $(x,y,z)$ 的细菌发生分裂,它会分裂产生 $6$ 个新细菌,分别前往坐标为 $(x+1,y,z),(x−1,y,z),(x,y+1,z),(x,y−1,z),(x,y,z+1),(x,y,z−1)$ 的小格。原来的细菌则死亡。特别地,如果一个细菌前往的小格并不存在,则该细菌会当场死亡。

实验将进行连续 $d$ 天。在 $d$ 天结束后,科学家们想知道:在坐标为 $(a,b,c)$ 的小格有多少细菌?由于答案可能很大,你只需要输出它对 $998244353$ 取模后的值即可。

输入格式

一行七个正整数 $d,n,m,k,a,b,c$。

输出格式

一行一个整数表示答案 $998244353$ 取模后的值。

输入输出样例 1

输入

2 2 2 3 1 1 1

输出

10

解释

第一天结束后,可以知道:所有 $z=2$ 的格子都恰有 $4$ 个细菌,其余格子都恰有 $3$ 个细菌。而第二天结束后,格子 $(1,1,1)$ 的细菌数量等于第一天结束时 $(1,1,2),(1,2,1),(2,1,1)$ 的细菌数量总和,即为 $10$。

输入输出样例 2

输入

2 2 2 3 1 1 2

输出

14

输入输出样例 3

输入

50 49 44 48 49 15 25

输出

544847893

输入输出样例 4

输入

120000 49997 49997 49993 46278 44140 26931

输出

139550295

数据范围与约定

对于全部数据,$1\leq d,n,m,k \leq 1.2 \times 10^5,1 \leq a \leq n,1 \leq b \leq m,1 \leq c \leq k$。

本题设有若干个子任务。对于每个子任务,你必须通过其中的全部测试点来获得这个子任务的分数。

  • 子任务 1($5$ 分):$d,n,m,k \leq 50$。
  • 子任务 2($10$ 分):$d,n,m,k \leq 5×10^3$。依赖子任务 1。
  • 子任务 3($15$ 分):$m=k=1$。
  • 子任务 4($10$ 分):$k=1$,$n,m \geq d$。
  • 子任务 5($15$ 分):$k=1$,$n,m \geq \frac{d}{10}$。依赖子任务 4。
  • 子任务 6($35$ 分):$k=1$。依赖子任务 3、4、5。
  • 子任务 7($10$ 分):无特殊限制。依赖子任务 1、2、3、4、5、6。

时空限制

时间限制:$\texttt{2s}$。

空间限制:$\texttt{512MB}$。