암호화

Ignas와 Simonas는 함께 고전 암호학에 흥미를 갖게 되어 서로에게 보내는 문자 메시지를 암호화하기로 했습니다. 두 사람이 정한 암호화 과정은 다음과 같습니다.

• 메시지에는 다음 기호들만 사용하며, 1부터 29까지 번호를 매깁니다.

  • 대문자 라틴 알파벳 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z는 알파벳 순서대로 1부터 26까지 번호를 매깁니다.
  • 공백 대신 사용하는 밑줄 _은 27번입니다.
  • 쉼표 ,와 마침표 .는 각각 28번과 29번입니다.

• 메시지는 기호 하나씩 다음과 같이 암호화합니다.

  1. 기호의 번호를 세제곱한 뒤 29로 나눈 나머지를 구하고, 그 나머지에 1을 더합니다.
  2. 1번에서 얻은 수를 번호로 갖는 새로운 기호를 찾습니다. 이것이 암호화된 기호입니다.

• 메시지의 모든 기호에 대해 같은 방식으로 계속합니다.

편의를 위해 기호 번호표를 아래에 제시합니다.

예를 들어, 텍스트 GERI_ORAI.는 이 알고리즘에 따라 YJDEVLDBEA로 암호화됩니다. 이는 쉽게 확인할 수 있습니다. 첫 글자 G를 봅시다.

• 글자 G의 번호는 7이고,
• 그 세제곱은 $7^3 = 343$이며,
• 343을 29로 나눈 나머지는 $343 \bmod 29 = 24$이고,
• 여기에 1을 더하면 $24 + 1 = 25$이며,
• 번호 25는 글자 Y에 해당합니다.

따라서 G를 암호화하면 Y가 됩니다. 다른 기호의 암호화도 같은 방식으로 확인할 수 있습니다.

번호가 29인 마침표 .는 글자 A로 암호화됩니다. $29^3$은 29로 나누어떨어지므로 나머지가 0이고, 1을 더하면 1, 즉 글자 A가 됩니다.

Ignas의 형은 이 암호화 알고리즘이 안타깝게도 매우 쉽게 "깨진다"는 것, 즉 암호문으로부터 원래 텍스트를 빠르게 복원(복호화)할 수 있다는 것을 알아차렸습니다.

이 알고리즘으로 암호화된 한 줄의 텍스트를 복호화하는 프로그램을 작성하세요.

암호화된 텍스트 문자열이 첫 번째 줄에 주어집니다.

복호화된 텍스트 문자열을 출력하세요.