暂无测试数据。

Description

给出 \(T\) 组询问，每组用 \(n,a,b,c,k_1,k_2\) 来描述。

对于每组询问，请你求出

\[\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}\]

对 \(10^9+7\) 取模。

Format

Input

第一行读入一个数 \(T\) 。

接下来 \(T\) 行，每行读入六个数 \(n,a,b,c,k_1,k_2\) 。

Output

输出共 \(T\) 行，每行一个答案。

答案对 \(10^9+7\) 取模。

Sample 1

Input

1
2 2 0 1 1 1

Output

10

Limitation

Data

对于 \(100\%\) 的数据，\(T = 1000\)，\(1 \le n, a, b, c \le {10} ^ 9\)，\(0 \le k_1 + k_2 \le 10\)。

Time and Space

1s, 125MB.

Source

loj #138

update by Shuchong