31788번 - 나무판자

문제

$N$그루의 나무가 각각 1ドル$씩의 간격을 두고 일직선으로 심어져 있다.

0ドル$일 차에 모든 나무의 높이는 0ドル$이고 나무가 자랄 때 너비는 1ドル$로 균일하다. 하루가 시작될 때 $i$번째 나무는 $p_i$ 퍼센트의 확률로 전날보다 높이가 1ドル$만큼 증가하고, 이외에는 전날과 같은 높이로 유지된다.

$N$개의 나무가 차지하는 영역 중 최대 크기의 직사각형 부분을 잘라내 커다란 나무판자를 얻으려 한다. 이때 나무판자의 두 변은 지면과 평행해야 한다.

예를 들어 5개의 나무가 심어져 있는 경우, 높이가 순서대로 1,4,2,5,3이면 나무판자의 크기는 8이다

$M$일 차에 얻을 수 있는 나무판자 넓이의 기댓값을 구하여라. 기댓값의 출력 형식은 출력 단락을 참고하여라.

입력

첫 번째 줄에 나무의 수 $N$과 기다리고자 하는 날 수 $M$이 주어진다. $(1 \leq N,M \leq 30)$

두 번째 줄에 각각의 나무가 매일 자랄 백분율 $p_1, p_2, \cdots, p_N$이 주어진다. $(1 \leq p_i \leq 100)$

주어지는 입력은 모두 정수임이 보장된다.

출력

나무판자의 넓이의 기댓값은 유리수이고, 기댓값을 기약분수 $\frac{y}{x}$의 꼴로 나타냈을 때 $x$는 998ドル,円 244,円 353$의 배수가 아님이 보장된다. 이때 $xz \equiv y \bmod{998,円 244,円 353}$이 되는 정수 0ドル \leq z < 998,円 244,円 353$가 항상 유일하게 결정된다. 이 $z$을 출력하시오.

제한

힌트