프로그램 명: mpvirus
제한시간: 1 초

그는 특이한 컴퓨터를 가지고 있는데, 그 컴퓨터는 정수 배열들 밖에 저장 할 수 없습니다.

그는 바이러스를 만들어 컴퓨터에 심었습니다. 그가 만든 바이러스는 매일 밤 자정에 활성화되어 메모리 속에 있는 모든 배열을 새로운 배열들로 바꾸는데, 그 새로운 배열들은 원래 배열의 모든 연속한 부분 배열입니다.

예를 들어, 오늘 메모리에 하나의 배열 (1,2,1,3)이 들어있다면, 내일은 메모리에 (1), (2), (1), (3), (1,2), (2,1), (1,3), (1,2,1), (2,1,3), (1,2,1,3)의 배열들이 들어있게 되는 것입니다.

그는 메모리에 들어있는 모든 배열을 지우고, 길이 N인 배열 하나를 넣었습니다.

그는 바이러스의 성능을 예상해 보기 위해 D일이 지난 후, 메모리에 들어있는 모든 배열의 원소들의 합을 미리 구하고 싶어 합니다. 그리고 이 합은 매우 커질 수 있기 때문에 이 합을 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하세요.

그의 컴퓨터는 메모리가 충분히 커서 바이러스로 인해 생성되는 모든 배열을 저장할 수 있으므로, 그에 대한 걱정은 하지 않아도 좋습니다.

입력

입력의 첫 번째 줄에는 테스트케이스의 개수를 의미하는 정수 T가 주어집니다. 각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 N(1≤N≤100,000)과 D(1≤D≤100,000)가 주어집니다. 두 번째 줄에는 처음에 메모리에 들어있을 배열 구성을 의미하는 N개의 음이 아닌 정수가 주어집니다. 단 메모리에 들어 있는 정수는 100,000이하입니다.

출력

처음에 메모리에 입력에서 들어온 배열만이 들어 있을 때 D일 후 바이러스에 의해 증식된 메모리에 들어있는 모든 원소의 합을 1,000,000,007로 나눈 나머지를 의미하는 정수 하나를 한 줄에 출력합니다.

입출력 예

입력

3
4 1
1 2 1 3
1 10
47
2 10
1 2

출력

34
47
33

출처:august14
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]