시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB70124815233.853%

문제

시대를 초월하는 검객 승균이는 자신의 문파 알프스검류를 단련하기 위해 신기술 천상용섬을 연마했다.

천상용섬은 눈앞의 \(N\)개의 물체를 베는 기술로써, 벨 때마다 베는 높이가 줄어들지 않고 유지되거나 증가한다.

천상용섬의 대단한 점은 물체를 베는 높이로 물체의 높이를 나누었을 때 항상 자연수로 나누어떨어진다는 점이다.

예를 들어 눈앞에 3개의 물체가 각각 2, 4, 6의 높이로 존재한다고 하자. 천상용섬은 이때 이 물체를 각각 높이 1, 2, 3 에서 벨 수 있다.

2는 1로, 4는 2로, 6은 3으로 나누어떨어지며, 높이가 줄어들지 않기 때문이다. 같은 이유로 1, 1, 1도 가능하다.

또한, 정확도를 자랑하기 위해 2, 4, 6의 높이를 베기도 한다. 즉, 물체의 높이만큼도 벨 수 있다. 단, 높이 0은 벨 수 없다.

승균이는 자신의 신기술 천상용섬이 어느 정도의 가능성을 품고 있는지 판단하기 위해 N개의 물체를 벨 수 있는 모든 경우의 수를 구하고자 한다. 위 예시의 경우 모두 12가지의 경우의 수가 존재한다.

그러나 승균이는 숫자를 배우지 못했기 때문에 이를 계산할 수 없다. 우리가 대신 경우의 수를 구해주자.

입력

입력은 여러 테스트케이스로 이루어져 있다.

첫째 줄에는 테스트케이스 개수를 나타내는 \(T\)가 주어진다. \((1 \le T \le 30)\)

각 테스트케이스의 첫째 줄에 물체의 개수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 300)\)

둘째 줄에 띄어쓰기를 간격으로 \(N\)개의 물체의 높이 \(H_i(1 \le i \le N)\)가 주어진다. \((1 \le H_i \le 1,000,000)\)

출력

테스트케이스마다 승균이가 벨 수 있는 모든 경우의 수를 출력한다. 출력은 개행으로 구분되어야 한다. 정답이 커질 수 있으니 \(1,000,000,007\)로 나눈 나머지를 출력한다.

예제 입력 1

2
3
2 4 6
2
2 3

예제 출력 1

12
3

출처

University > 전북대학교 > 2016 전북대 프로그래밍 경진대회 D번