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)	\
    VH-2		VH-2
    \		/

• 루트. 이때 E는 다음과 같은 형태이며, eval(E) = min{0 ≤ x < p : x⁴ = eval(E')² mod p}으로 정의합니다. E의 너비는 (L+3), 높이는 (H+1)이 됩니다.

  S(H,2)		+	길이 L의 -로만 이루어진 문자열
  		VH-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가 됩니다.

  E1 (너비 L1, 높이 H)	S(H,1)	S(⌊H/2⌋,1)	S(H,1)	E2 (너비 L2, 높이 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)	E1 (너비 L, 높이 H1)	S(H1,1)
  길이 (L+2)의 -로만 이루어진 문자열
  S(H2,1)	E2 (너비 L, 높이 H2)	S(H2,1)

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

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

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

R = 1, C ≤ 10³.

R ≤ 10³, C ≤ 10³.