给定一个长度为 的二进制数组 （每个元素为 或 ）。记 为奇数。对于数组 的所有长度恰为 的子序列，求它们中位数之和，并对 取模。 【名词解释】 子序列：如果 可以从 中删除几个元素（可能是零，也可能是全部元素），那么数组 就是数组 的子序列。子序列不必是连续的。 中位数：长度为奇数 的数组的中位数是排序后的第 个元素。

输入描述:

第一行输入整数 表示测试用例个数。 对于每个测试用例： 第一行输入两个整数 ，满足 且 为奇数； 第二行输入 个整数 。 保证所有测试用例的 之和不超过 。

输出描述:

对每个测试用例输出一行一个整数，表示所有长度为 的子序列中位数之和模 的结果。