16645번 - Fraction Challenge

문제

사람들은 좋아하는 수가 무엇이냐고 물었을 때 주로 자연수를 대답합니다. 그래서 키파도 평소에는 자연수에 관한 얘기를 많이 하지만, 사실 키파는 분수도 엄청 좋아합니다.

키파가 좋아하는 분수를 모두 곱하면 키파가 아주 좋아하는 분수가 만들어집니다. 키파는 이 분수를 외울 것이기 때문에 분자나 분모가 너무 길어지는 것을 걱정했습니다. 운이 좋았던 건지 머리가 좋았던 건지, 그 곱을 기약분수로 표현했을 때 분자와 분모가 모두 10⁹을 넘지 않았습니다.

키파가 아주 좋아하는 분수를 만들어 키파를 행복하게 해 줍시다.

입력

첫째 줄에 키파가 좋아하는 분수의 개수 n이 주어집니다.

둘째 줄부터 n개의 줄에 키파가 좋아하는 분수가 주어집니다. 한 줄에는 하나의 /가 있습니다. 각 줄은 /로 시작하거나 끝나지 않으며, 이 줄의 /를 제외한 모든 문자는 숫자입니다. 이 줄이 의미하는 분수는 / 왼쪽에 있는 십진법 수를 a, 오른쪽에 있는 십진법 수를 b라 할 때 ^a/_b입니다. 각 줄의 맨 첫 숫자와 / 직후의 숫자는 0이 아님이 보장되며, a와 b의 소인수는 10⁹을 넘지 않음이 보장됩니다.

둘째 줄부터 n개의 줄에 주어지는 숫자의 개수의 합은 2,000,000개를 넘지 않습니다.

출력

첫째 줄에 키파가 아주 좋아하는 분수를 a/b 형태로 출력합니다. 기약분수로 출력해야 하며, 답으로 출력하는 분수의 분자와 분모는 모두 10⁹ 이하임이 보장됩니다.

제한

힌트