纸船效应

Problem Description

有 $n$ 个怪物排成一排。其中从左到右第 $i$ 个怪物的生命值为 $a_i$。一个生命值为 $x$ 的怪物 $A$ 可以吃掉一个生命值为 $y$ 的怪物 $B$，当且仅当 $x > y$。在吃掉 $B$ 之后，$A$ 的生命值会变为 $x+y$。 定义一个怪物序列是好的，当且仅当序列中最左侧的怪物可以从左到右依次吃掉序列中的所有其他怪物。例如序列 （$7,4,8$） 是好的，因为生命值为 $7$ 的怪物可以先吃掉生命值为 $4$ 的怪物，生命值变为 $11$，再吃掉生命值为 $8$ 的怪物。而序列 （$7,8,4$） 不是好的，因为生命值为 $7$ 的怪物无法吃掉生命值为 $8$ 的怪物。特殊的，如果序列中只有一个怪物，我们也认为这个序列是好的。 定义一个怪物序列 $a_1,a_2,\dots a_n$ 的权值为 $k^c$。其中 $k$ 是一个给定的正整数，$c$ 为序列 $a$ 中好的非空子区间的个数。 cats 有 $n-1$ 种魔法药水，其中第 $i$ 种魔法药水可以使第 $i$ 个怪物的生命值减少 $h_i$，同时使第 $i+1$ 个怪物的生命值增加 $h_i$。在计算序列 $a$ 的权值之前，cats 可以自由选择是否使用每个魔法药水。 现在，cats 想知道在全部的 $2^{n-1}$ 种情况（使用或者不使用每个魔法药水）下序列 $a$ 的权值之和。你能帮 cats 求出答案吗？由于答案可能很大，你只需要求出答案对 $10^9+7$ 取模后的结果。

Input

第一行包含一个整数 $T$ （$1\leq T \leq 1000$），表示一共有 $T$ 组测试数据。 对于每组测试数据： 第一行为两个整数 $n,k$ （$2\leq n\leq 150,1\leq k < 10^9 + 7$），表示怪物序列的长度和权值参数 $k$。 第二行为 $n$ 个整数 $a_1,a_2,\dots,a_n$ （$2\leq a_i \leq 5\cdot 10^{15}$），表示每个怪物的生命值。 第三行为 $n-1$ 个整数 $h_1,h_2,\dots h_{n-1}$ （$1\leq h_i < a_i$），表示每个魔法药水的参数。 保证所有测试数据的 $n^3$ 之和不超过 $10^7$。

Output

对于每组测试数据，输出一个整数，表示所有情况下序列 $a$ 的权值之和。答案对 $10^9 + 7$ 取模。

Sample Input

2
3 2
7 4 8
6 1
10 142857
314 159 265 358 979 3238 4626 4338 3279 5028
200 100 200 300 700 1700 3000 1100 2000

Sample Output

88
369217665

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）