题目描述

在一个遥远的国度，有一个聪明的数学家叫做牛宝宝。他最近发现了一个有趣的数学问题，与一种特殊的数列有关。这个数列有一个特殊的生成方式，每一个数都是由前一个数通过一个特定的递推公式计算出来的。牛宝宝对这个数列的“差异和”非常感兴趣，也就是这个数列中任意两个不同数的差的绝对值之和。

为此牛宝宝有一个函数：

long long GetDiffSum( int a[], int n ) {
    long long sum = 0;
    int i, j;
    for( i = 0; i < n; i++ )
        for( j = i + 1; j < n; j++ )
            sum += abs( a[i] - a[j] );
    return sum;
}

其中a[i]的值可由下面的递推公式得出： a[i] = (K * a[i-1] + C) % 1000007 ,i > 0

现在给出K,C,n,a[0]的值，你需要找出 long long GetDiffSum( int a[], int n ) 这个函数的值

输入格式

第一行仅有一个整数T(T<=100)代表数据组数。 对于每组数据，在一行中有4个正整数依次表示K, C, n ,a[0]

输出格式

对于每组数据，输出函数结果。

2

1 1 2 1

10 10 10 5

1
7136758

对于20%的数据，保证n≤100

对于50%的数据，保证n≤10000

对于100%的数据，保证1≤K,C,a[0]≤10^4 ,2≤n≤10^5