描述

马尔可夫猫猫问题是指: 给定环形区域，平分$n$份，按顺时针从$1$编号。猫猫初始时刻($T=0$)在位置编号$i$上，每个整数时刻可以决定猫猫往前（顺时针）还是往后（逆时针）移动。猫猫有选择困难症，所以它只会等概率随机地选择向前还是向后移动，但不会不移动。

求经过时间$t$后，猫猫在编号$j$的数论概率。

输入

给定样例数$\ N(1\le N\le10^4)$

对于每个样例: 给定一行四个正整数$\ n, i, j, t\ (3\le n\le10,\ 1\le i\le n,\ 1\le j\le n,\ 1\le t\le10^9)$

输出

按题目要求输出。其中，数论概率是指，对于一个$\frac{x}{y}$的形式的有理数结果，求出对应的$x\cdot y^{-1}\pmod{998244353}$，其中，$y^{-1}$表示$y$关于$998244353$的数论倒数，如$\frac{1}{3}:=332748118$。

样例

input

4
3 1 3 5
5 1 3 199
4 4 3 824275688
10 4 10 842441898

output

655097857
59717054
0
640212300