18166번 - Evaluation 서브태스크

문제

식을 평가해 봅시다!

입력

첫 줄에 행의 개수 R와 열의 개수 C가 주어집니다.

둘째 줄부터 R개의 줄 각각에 C개의 문자가 주어지는 형태로 표현식 E₀가 주어집니다. E₀의 너비는 C, 높이는 R임이 보장됩니다.

먼저 다음과 같은 두 개의 그림을 정의합니다.

• S_(r,c)는 너비 c, 높이 r의 공백 ""으로만 이루어진 그림입니다.
• V_h는 너비 1, 높이 h의 |로만 이루어진 그림입니다.

이를 이용해 표현식 E를 다음 중 하나와 같이 정의합니다.

• 수. 이때 E는 다음과 같은 형태이며, eval(E) = n mod p으로 정의합니다. n ≥ 0이 되도록 주어집니다. 이때 h₁, h₂ ≥ 0을 만족하며, E의 너비는 L, 높이는 (h₁+h₂+1)이 됩니다.
  S_(h1,L)
  n (길이 L)
  S_(h2,L)
• 괄호. 이때 E는 다음과 같은 형태이며, eval(E) = eval(E')으로 정의합니다.
  • 만일 E'의 높이가 1이면, 다음과 같이 정의하여 E의 너비는 (L+2), 높이는 1이 됩니다.
    ( E' (너비 L) )
  • 만일 E'의 높이가 H ≥ 2이면, 다음과 같이 정의하여 E의 너비는 (L+2), 높이는 H가 됩니다.
    / E' (너비 L) \
    V_H-2 V_H-2
    \ /
• 루트. 이때 E는 다음과 같은 형태이며, eval(E) = min{0 ≤ x < p : x⁴ = eval(E')² mod p}으로 정의합니다. E의 너비는 (L+3), 높이는 (H+1)이 됩니다.
  S_(H,2) + 길이 L의 -로만 이루어진 문자열
  V_H-1 E' (너비 L, 높이 H)
  / \ |
• 연산. 이때 E는 다음과 같은 형태이며, op는 +, -, *, / 중 하나입니다. 연산자 op에 따라 eval(E) = (eval(E₁) op eval(E₂)) mod p로 정의합니다. 이때 eval(E₁) / 0 = 19981204로 정의합니다. E의 너비는 (L₁+L₂+3), 높이는 H가 됩니다.
  E₁ (너비 L₁, 높이 H) S_(H,1) S_{(⌊H/2⌋,1)} S_(H,1) E₂ (너비 L₂, 높이 H)
  op
  S_{(⌊(H-1)/2⌋,1)}
• 분수. 이때 E는 다음과 같은 형태이며, eval(E) = (eval(E₁) / eval(E₂)) mod p로 정의합니다. 이때 E의 너비는 (L+2), 높이는 (H₁+H₂+1)이 됩니다.
  S_(H1,1) E₁ (너비 L, 높이 H₁) S_(H1,1)
  길이 (L+2)의 -로만 이루어진 문자열
  S_(H2,1) E₂ (너비 L, 높이 H₂) S_(H2,1)

위의 모든 식에서, p = 10⁹ + 7로 소수입니다.

입력은 위 규칙을 통해서 어떠한 경우에도 둘 이상의 parse tree가 생성되지 않도록 주어집니다.

출력

eval(E₀)를 출력합니다.

제한

서브태스크 1 (30점)

R = 1, C ≤ 10³.

서브태스크 2 (70점)

R ≤ 10³, C ≤ 10³.

힌트