You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

牛宝宝有一个函数：

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$