셀 병합 timer 2s memory 1024MB

정올이는 유명한 온라인 게임을 하고 있습니다. 게임에서는 여러 개의 셀들이 서로 격돌하여 하나의 최종 셀만 남게 됩니다. 각 셀은 다른 셀에 의해 먹히면서 합쳐집니다. 이 과정에서 최종적으로 승리할 셀의 레이블을 구하는 문제입니다.

게임의 규칙은 다음과 같습니다:

• 셀들은 N개가 주어지며, 각 셀은 1번부터 N번까지 레이블을 가지고 있고, 크기는 s_1, s_2, \dots, s_N로 주어집니다.

• 셀들이 합쳐지는 규칙은 다음과 같습니다. 두 개의 인접한 셀을 임의로 선택하여 하나의 셀로 합칩니다. 두 셀이 합쳐질 때, 각 셀의 레이블과 크기를 비교하여 새로운 셀의 레이블과 크기를 결정합니다:

  • 레이블이 작은 셀과 큰 셀이 합쳐지면, 결과 셀의 레이블은 큰 셀의 레이블로 결정됩니다.

  • 만약 크기가 같다면, 레이블이 더 큰 셀이 새로운 셀의 레이블이 됩니다.

각 레이블에 대해 최종적으로 그 레이블을 가진 셀이 남을 확률을 구해야 합니다.

확률은 \frac{a_i}{b_i} 형태로 주어집니다. 여기서 b_i는 10^9+7로 나눈 나머지가 0이 아닌 값입니다. 그러므로 각 확률을 a_i \times b_i^{-1} \mod (10^9+7) 형태로 출력해야 합니다.