题目描述

现在有一张 $ka\times kb\times kc\times kd$ 的四维网格，每个格子只能是黑色或白色。

请问：对于其中每个 $k\times k\times k\times k$ 的网格，都恰好有 $1$ 个格子是黑色的颜色分布方案有几种？

由于答案可能很大，你只需要输出方案数对 $998244353$ 取模后的结果。

输入格式

第一行输入一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行输入五个整数 $k,a,b,c,d$，保证 $a\le b\le c\le d$。

输出格式

输出 $T$ 行，每行一个整数，表示对应询问的答案对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

1
3 2 2 2 2

输出 #1

744944653

说明/提示

数据范围与约定

本题采用捆绑测试，各子任务限制如下。表中已经将原题中的“同上”条件展开写明。

对于全部数据，保证 $1\le T\le 3$，$1\le k<998244353$，$2\le a\le b\le c\le d\le 10^{18}$。