욕망

거짓말을 하는 거짓 증인이여!

n개의 정수를 포함하는 수열이 주어진다. 처음에 0인 변수 res가 있다. 다음 과정을 k번 반복한다.

1부터 n까지의 인덱스 중 하나를 균등한 확률로 무작위 선택하고, 이를 x라고 하자. 1 ≤ i ≤ n이지만 i ≠ x인 모든 ai의 곱을 res에 더한다. 그런 다음 ax에서 1을 뺀다.

과정이 끝났을 때 res의 기댓값을 구해야 한다. res의 기댓값은 기약분수 로 나타낼 수 있음이 증명되어 있다. 를 구해야 한다.

첫 번째 줄에는 원소의 개수와 문제에서 명시된 매개변수 k를 나타내는 두 정수 n와 k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 109)가 주어진다.

두 번째 줄에는 공백으로 구분된 n개의 정수 a1, a2, ..., an (0 ≤ ai ≤ 109)가 주어진다.

값 를 하나의 정수로 출력한다.