Scooby is a great mathematician and loves playing with sequences. He has a sequence whose ith term is given as follows:

Ti = i^{k} - (i-1)^{k}

where k is an integer. You have to find the sum of first N terms of the series. In order words you need to find the value of the following expression :

T1+T2+…TN. As this value can be really large, output the value modulo 10^9+7.

**Constraints:**

```
Number of testcases T: 1<=T<=1000
1<=N<=1000000000
1<=K<=1000000000
```

**Input:**

```
An integer N
An integer K
```

**Note:**

```
Your code will run against multiple testcases.
```

**Output:**

```
One integer corresponding to the value of the above mentioned expression modulo 1000000007.
```

**Examples:**

Input:

```
3
2
```

Output:

```
9
```

Explanation:

```
The three terms of the sequence are :
T1=1
T2=3
T3=5
Threfore the value of T1+T2+T3 is 9 and hence the answer is 9.
```

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**The Sequence game**

to access hints and editorial solutions for

Loading...