전구

토마스 에디슨은 더 나은 전구를 만들기 위해 연구하고 있다. 이번 실험에서는 전구 묶음으로 넓은 면을 채우고 테스트를 진행한다. 그는 $N$개의 행을 만들고, 각 행에 $M$개의 전구를 배치했다. 각 전구는 확률 $P$로 작동한다. 작동하지 않는 전구는 고장 난 것이며 켜지지 않는다. 토마스는 작동하는 전구가 가로로 이어진 가장 긴 구간의 길이에 대한 기댓값을 구하려 한다.

예를 들어 아래 격자에서 1은 작동하는 전구, 0은 고장 난 전구이다. 작동하는 전구가 가로로 이어진 가장 긴 구간의 길이는 3이다. 두 번째 행에 연속된 1이 세 개 있고, 네 번째 행에도 연속된 1이 세 개 있다.

1 0 1 1
0 1 1 1
0 1 0 0
1 1 1 0
1 1 0 1

가로 방향의 구간만 고려한다.

한 줄에 세 개의 수가 공백으로 구분되어 주어진다. 양의 정수 $N$과 $M$, 그리고 실수 $P$이다.

문제의 답을 출력한다. 절대 오차 또는 상대 오차가 $10^{-4}$보다 작으면 정답으로 인정한다.

• $1 \le N, M \le 2000$
• $0 \le P \le 1$