Problem Description

前两段和第二题相同，但你不需要阅读第二题就可以完成这个题目。

你有一个数字 $x$ 和若干个操作，每个操作是 $+a_i$ 或者乘 $\times a_i$ 中的一种。你可以重新排列这些操作的顺序，然后对数字 $x$ 执行这些操作。

比如说三个操作是 $+a_1, +a_2, \times a_3$。如果按顺序执行这三个操作，那么得到的结果是 $((x+a_1)+a_2) \times a_3$。如果排列成 $+a_2, \times a_3, +a_1$，那么得到的结果是 $((x+a_2) \times a_3)+a_1$。

令 $P=10^9+7$。给定数字 $x$ 和 $n$ 个操作，想知道我们将这些操作重新排列之后，得到的结果对 $P$ 取余之后得到最小值是多少。

Input

本题有多组测试数据。

第一行一个整数 $T(1 \leq T \leq 1000)$ 表示数据组数。

对于每组数据，第一行两个整数 $n, x(1\leq n\leq 10, 0\leq x \le P)$。接下来 $n$ 行，每行包含一个运算符和数字 $a_i(0\leq x \le P)$，数字和运算符之间用空格隔开。

在测试数据中，保证 $n=10$，$x, a_i$ 在 $[0, P-1]$ 之间独立均匀随机，运算符在`+, *` 这两种里面随机。

Output

对于每组数据输出一行，表示答案。

1
10 671872738
* 683201291
* 250712304
+ 559804065
+ 329491176
+ 948072486
+ 821736719
+ 67290733
+ 947904529
+ 962738511
* 712203548

7712