구거법으로 검산하기

위대한 수학자 피사의 레오나르도 피보나치(1170–1240)에 대해 들어보았을 것이다. 그가 1202년에 처음 출간한 책 Liber Abaci에서 설명한 여러 알고리즘 가운데에는 덧셈·뺄셈·곱셈을 검산하는 "구거법(casting out nines)" 절차가 있다. 역사학자들에 따르면 이 절차는 아랍인을 거쳐 유럽에 전해졌지만 실제로는 인도 아대륙에서 개발된 것으로 보이며, 그래서 "힌두 검산(Hindu check)"이라고도 불린다.

구거법은 합동식 $10 \equiv 1 \pmod 9$을 이용하는 기초적인 검산법이다. $x \equiv y \pmod z$라고 쓰면 이는 $x \bmod z$와 $y \bmod z$가 같다는 뜻임을 기억하자.

자연수 $a$, $b$의 곱을 $c$라 하고, $a$, $b$, $c$의 각 자리 숫자의 합을 각각 $\bar a$, $\bar b$, $\bar c$라 하자. 그러면 $a \equiv \bar a \pmod 9$, $b \equiv \bar b \pmod 9$, $c \equiv \bar c \pmod 9$가 성립한다. 또한 $a \times b \equiv \bar a \times \bar b \pmod 9$이므로 $\bar a \times \bar b \equiv \bar c \pmod 9$이다. 따라서 $c$와 $\bar a \times \bar b$가 $9$를 법으로 하여 합동이 아니라면 그 곱셈은 잘못 계산된 것이다.

예를 들어 $12345 \times 67890 = 838102050$이다. $12345$와 $67890$의 자리합은 각각 $15$와 $30$이고 그 곱은 $450$이다. $838102050$의 자리합은 $27$이다. $450 \equiv 27 \equiv 0 \pmod 9$이므로 검산이 일치한다.

다른 예로, 어떤 사람이 $13579 \times 24680 = 334129720$이라고 잘못 계산했다고 하자. 이때 $\bar a \times \bar b = 25 \times 20 = 500 \equiv 5 \pmod 9$인 반면 $\bar c = 31 \equiv 4 \pmod 9$이므로 이 곱셈은 확실히 틀렸다.

$a + b \equiv \bar a + \bar b \pmod 9$이 성립하므로 이 검산법은 덧셈에도 똑같이 적용할 수 있다.

주어진 덧셈 또는 곱셈이 힌두 검산을 통과하는지 판정하는 프로그램을 작성하라.

프로그램은 하나 이상의 테스트 케이스로 시험된다. 각 테스트 케이스는 한 줄에 다음 형식으로 주어진다.

a+b=c.

또는

a*b=c.

줄 끝의 .에 주의하라. $a$, $b$, $c$는 자연수이다. 숫자와 기호(+, *, =, .) 사이에는 공백이 없지만 . 뒤에는 공백이 올 수 있다.

입력의 마지막 줄은 . 하나만 있는 줄이며 테스트 케이스에 포함되지 않는다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

k. result

여기서 $k$는 테스트 케이스 번호(1부터 시작)이고, result는 해당 덧셈 또는 곱셈이 힌두 검산을 통과하면 PASS, 그렇지 않으면 NOT!이다.