该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

牛宝宝有一个函数：

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

见附件

见附件

附件

file

提示

对于20%的数据，保证$n \le 100$

对于50%的数据，保证$n \le 10000$

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