Máy tính của Trung hôm nay bị virut rất lạ và nó tấn công vào bộ nhớ của máy tính. Cụ thể là khi Trung lưu trữ dữ liệu mảng trong bộ nhớ máy tính, thì cứ sau ~1~ giây virut nhân bản dữ liệu mảng bằng một loạt các mảng con liền kề liên tiếp của nó. Ví dụ ~a=\{1, 2, 3, 4\}~ sẽ thay bằng ~a=\{\{1\}, \{2\}, \{3\},\{4\}, \{1, 2\}, \{2, 3\}, \{3, 4\}, \{1, 2, 3\}, \{2, 3, 4\}, \{1, 2, 3, 4\} \}~.

Bài toán hôm nay Trung đặt ra cho các bạn là với một mảng ~a~ gồm ~n~ phần tử cho trước. Hỏi sau ~t~ giây thì tổng các phần tử của mảng đang có là bao nhiêu?

Input

Dòng thứ nhất là số nguyên ~T~ là số testcase thỏa ~1 \le T \le 10~. Mỗi testcase của ~T~ bao gồm:

• Dòng thứ nhất chứa hai số nguyên ~n, t~ thỏa ~n\le 50, t \le 1000~.

• Dòng thứ hai chứa dãy số ~a_1, a_2, \ldots a_n~ là các số nguyên không âm có giá trị nhỏ.

Output

Ứng với mỗi testcase in tổng cần tính. Tuy các phần tử ~a_i~ có giá trị nhỏ nhưng tổng vẫn lớn nên cần modulo cho ~10^9+7~.

Samples

Sample Input 1

3
4 1
1 2 3 4
1 10
5
2 2
1 2

Sample Output 1

50
5
9