숫자 맞히기
시간 제한2초메모리 제한256 MB
위치 i, j와 정수 k가 주어질 때, k를 곱하면 소수점 아래 i번째와 j번째 자리가 서로 바뀌는 0과 1 사이의 유리수 x를 기약분수로 구하거나 해가 없음을 판정한다.
문제
최근 한 인기 소셜 네트워크에 "숫자 맞히기!"라는 앱이 등장했다. 이 앱의 사용자에게는 여러 레벨로 이루어진 게임이 주어지는데, 각 레벨에서 주어진 정보를 바탕으로 숨겨진 수를 알아내야 한다.
그중 가장 어려운 레벨 중 하나에서는 유리수 x(0 < x < 1)를 맞혀야 한다. 이 수에 대해서는 자연수 k를 곱한 결과의 십진 표기에서 정확히 한 가지 변화가 일어났다는 사실이 알려져 있다. 즉, 소수점 아래 i번째 자리와 j번째 자리의 숫자가 서로 바뀌었다(자릿수는 소수점 바로 뒤부터 왼쪽에서 오른쪽으로 1부터 번호를 매긴다). 소수점 앞의 숫자는 바뀌지 않았으므로 0 < kx < 1이 성립한다. 참고로 x의 십진 표기는 소수점 아래 자릿수가 무한히 많을 수 있다.
여러분이 할 일은 i, j, k가 주어졌을 때 x의 값을 구하는 프로그램을 작성하는 것이다.
입력
첫째 줄에 세 정수 i, j, k가 주어진다(1 ≤ i < j ≤ 1000, 2 ≤ k ≤ 10^9).
출력
조건을 만족하는 수가 존재하면, 그 수를 나타내는 기약분수의 분자 a와 분모 b를 공백으로 구분해 출력한다(a, b > 0). 존재하지 않으면 NO SOLUTION을 출력한다.