Sweets were distributed on the occasion of Independence Day, and mess contractor was busy in distributing sweets and forgot to count the total number of sweet distributed.
He knows that there were N numbers of students and the event lasted for about D days. The ith student ate one sweet at 1st day, Ai+1, 2*Ai+1 .... (turn-1)*Ai+1 day from the beginning of the sweet distribution. Help him find the total number of sweets distributed.
Constraints:
1 <= T <= 10
1 <= N <= 105
1 <= Ai <= 106
1 <= D <= 109
Input:
The first line contains the number of test cases T while the following line has space separated two numbers - N and D. Next line contains N-space separated number separated Ai for every student.
N - Number of Students
D - Event duration in days
Ai - Hungriness Constant for Students
Output:
For every test case output the number of sweets that were distributed by the mess contractor on a new line,
NOTE: Since the number can be large take the modulo with 1e9+7. (1000000007)
Student Eating sweet at day,
first student eats at day: 1 2 3 4 5 6 7 8 9 10
second student eats at day: 1 3 5 7 9
third students eats at day: 1 4 7 10
fourth students eats at day: 1 5 9
Fifth students eats at day: 1 6
