问题描述

菜哭武最近得到了一套卡牌，每天都喜欢拉着自己的同事们做一些游戏。这次，他拿出了 $N$ 张，上面印着整数的卡牌，上面的数字依次是 $a_1, a_2, a_3 \ldots a_n$。

他知道，从这里面取任意多张牌，一共有 $2^N$ 种方法，除了什么都不取的那一种，其他的可以计算出这些卡牌上面数字的和。现在他想知道，这 $2^N - 1$ 种方法里，数字和最小的 $K$ 种都是多少。希望你能帮帮他啊。

输入格式

题目包含多组数据。

输入的第一行有一个整数 $T$ ($1 \leq T \leq 10$) 代表有 $T$ 组数据。

对于每组数据分为两行：

第一行有两个整数 $N$，$K$（其中 $1 \leq N \leq 200000$, $1 \leq K \leq \min(2^N - 1, 200000)$），

第二行有 $N$ 个整数，分别是 $a_1, a_2, a_3 \ldots a_n$（$-10^8 \leq a_i \leq 10^8$）。

输出格式

对于每组数据，输出的第一行为 Case #x: ，其中 $x$ 是数据编号（从 $1$ 开始），

第二行输出一个非负整数，为正常需要输出的 $K$ 的数字的和 $\bmod 99989$ 的结果。

样例输入

2
2 1 
1 1 
3 3
-1 0 1

样例输出

Case #1:
1
Case #2:
99987

提示

本题因为输出较大，在 OJ 评测会出现输出超限的问题，现场赛时采用了手工评测。现在已修改输出格式，请各位注意。