시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 23 3 3 25.000%

문제

식을 평가해 봅시다!

입력

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

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

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

  • S(r,c)는 너비 c, 높이 r의 공백 " "으로만 이루어진 그림입니다.
  • Vh는 너비 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) \
      VH-2 VH-2
      \ /
  • 루트. 이때 E는 다음과 같은 형태이며, eval(E) = min{0 ≤ x < p : x4 = eval(E')2 mod p}으로 정의합니다. E의 너비는 (L+3), 높이는 (H+1)이 됩니다.
    S(H,2) + 길이 L-로만 이루어진 문자열
    VH-1 E' (너비 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 (30점)

R = 1, C ≤ 103.

서브태스크 2 (70점)

R ≤ 103, C ≤ 103.

예제 입력 1

6 10
/   +--- \
|   | 6  |
|   |--- |
| /\| 3  |
|--------|
\ 12 - 9 /

예제 출력 1

353237869

출처

Contest > 키파컵 > 제2회 키파컵 E번

  • 문제를 만든 사람: kipa00

채점

  • 예제는 채점하지 않는다.