12028 - A Gift from the Setter

下列程式碼是計算陣列 a[] 中任兩數之差值的和：

a[]內的元素是依下列式子所決定：

a[i] = (K*a[i - 1] + C)%1000007 for i > 0

給定K, C, a[0] 及陣列長度 n 之值，請你計算下列函式之回傳值：

long long GetDiffSum( int a[], int n )

不過上面提供的程式碼的效率實在是太慢了，直接套用的結果很可能會讓你得到"TLE"，所以你有必要對此做最佳化。

Input

輸入一開始會給定整數T( <= 100)表示測試資料的組數。每組資料有四個整數K, C, n, a[0] 其中1 <= K, C a[0] <= 10000 且 2 <= n <= 100000。

Output

請輸出測試資料編號與GetDiffSum之回傳值。

Sample Input 

2
1 1 2 1
10 10 10 5

Sample Output 

Case 1: 1
Case 2: 7136758

---

原文出處