小苯的左右移动

题号：NC305088
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯拿到了一个整数 $k$ ，接着他按顺序对 $k$ 执行了恰好 $n$ 次操作，具体的：
$\hspace{15pt}$ 给定一个长度为 $n$ 的序列描述这 $n$ 次操作（编号从 $1$ 到 $n$ ），其中第 $i$ 次操作为：

$\hspace{23pt}\bullet$ 如果 $i$ 是奇数，则执行： $\rm k=k\ll a_i$ 。（其中 $\ll$ 表示位运算中的左移运算符。）
$\hspace{23pt}\bullet$ 如果 $i$ 是偶数，则执行： $\rm k=k\gg a_i$ 。（其中 $\gg$ 表示位运算中的右移运算符。）

$\hspace{15pt}$ 这 $n$ 次操作将按顺序一个个执行，你的任务就是确定最终 $k$ 的值。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行两个整数 ，分别表示操作的个数，以及小苯拿到的初值 。
第二行  个整数 ，表示

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：
在单独的一行输出一个整数，表示最终  的值。（由于答案可能很大，因此输出答案对  取模的值。）

示例1

输入

复制

输出

复制

96
6

说明

对于第一组测试数据，，二进制为：。

经过  次操作， 的二进制变化为：.

最终  的二进制为 ，其十进制为 。