Evaluation

시간 제한2초메모리 제한512 MB

요약
ASCII 아트로 그려진 산술식을 파싱해 소수 p = 10^9+7로 나눈 나머지를 계산한다. 괄호, 루트, 사칙연산, 분수 구조를 복원하고 0으로 나누면 19981204를 결과로 둔다.
난이도

어려움10점 중 9점

유형
구현, 재귀, 수학, 정수론
정답자
아직 제출이 없습니다

문제

식을 평가해 봅시다!

입력

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

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

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

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

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

  • 수. 이때 E는 다음과 같은 형태이며, eval(E) = n mod p으로 정의합니다. n ≥ 0이 되도록 주어집니다. 이때 h1, h2 ≥ 0을 만족하며, E의 너비는 L, 높이는 (h1+h2+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-2V**H-2
      \/

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

    S(H,2)+길이 L의 -로만 이루어진 문자열
    V**H-1E' (너비 L, 높이 H)
    /\|

  • 연산. 이때 E는 다음과 같은 형태이며, op는 +, -, *, / 중 하나입니다. 연산자 op에 따라 eval(E) = (eval(E1) op eval(E2)) mod p로 정의합니다. 이때 eval(E1) / 0 = 19981204로 정의합니다. E의 너비는 (L1+L2+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(E1) / eval(E2)) mod p로 정의합니다. 이때 E의 너비는 (L+2), 높이는 (H1+H2+1)이 됩니다.

    S(H1,1)E1 (너비 L, 높이 H1)S(H1,1)
    길이 (L+2)의 -로만 이루어진 문자열
    S(H2,1)E2 (너비 L, 높이 H2)S(H2,1)

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

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

출력

eval(E0)를 출력합니다.

예제1

  1. 예제 1

    입력
    6 10
/   +--- \
|   | 6  |
|   |--- |
| /\| 3  |
|--------|
\ 12 - 9 /
    예상 출력
    353237869