승계

비토는 뉴욕의 여러 지역에서 단순한 올리브유 사업부터 더 위험한 상품까지 다양한 사업을 벌였다. 경쟁은 말 그대로 목숨을 건 싸움이었고, 비토는 이동 중에 가장 취약했다. 그래서 그는 이동에 쓰는 도로 일부를 소독했다. 소독된 도로만으로 자신의 지역 중 어느 두 곳이든 오갈 수 있게 하려는 것이었다. 소독 작업은 비용이 매우 커서, 참모는 필요한 최소한의 도로만 소독하도록 했다.

비토가 늙어 아들 마이클에게 사업을 넘겼다. 카포들도 사업의 몫을 원했다. 그래서 마이클은 자신을 위해 정확히 $K$개의 지역을 고르고, 나머지는 카포들이 갖기로 했다. 마이클은 손해를 보는 지역도 포함해 각 지역의 사업 가치를 계산했다. 그는 고른 $K$개 지역의 사업 가치 합이 최대가 되면서, 그 지역들끼리 소독된 도로만으로 어느 두 곳이든 오갈 수 있기를 원한다. 또한 자신의 지역이 아닌 곳은 지나가고 싶지 않다. 즉, 고른 지역은 도로망에서 연결된 부분이어야 한다.

가능한 최대 사업 가치 합을 구하라. 그 값을 얻는 방법의 수도 구하라. 방법의 수는 1000000007로 나눈 나머지로 답한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 공백으로 구분된 세 정수 $N$, $K$, $R$이 주어진다. $N$은 지역의 수, $K$는 마이클이 고를 지역의 수, $R$은 소독된 도로의 수이다. 다음 줄에는 $N$개의 정수가 주어지며, $i$번째 정수는 $i$번째 지역의 사업 가치이다. 이어서 $R$개의 줄에 각각 두 정수 from과 to(모두 0부터 시작)가 주어진다. 이는 지역 from과 지역 to 사이에 양방향 소독 도로가 있다는 뜻이다.

각 테스트 케이스마다 공백으로 구분된 두 정수를 한 줄에 출력한다. 첫 번째 정수는 가능한 최대 사업 가치 합이다. 두 번째 정수는 그 값을 얻는 방법의 수를 1000000007로 나눈 나머지이다.

• $1 \le T \le 100$
• $1 \le K \le N \le 100$
• 각 지역의 사업 가치는 $-1000$ 이상 $1000$ 이하이다.
• $0 \le from, to < N$이며, $from$과 $to$는 서로 다르다.
• 같은 두 지역을 잇는 도로는 없다.
• 도로는 모든 지역 쌍을 연결하며, 도로를 하나라도 제거하면 연결되지 않는 지역 쌍이 생긴다.