시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB103093017204726.779%

문제

박성원은 이 문제를 풀지 못했다.

서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {5221,40,1,58,9}로 5221401589를 만들 수 있다. 합친수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오.

하지만, 박성원은 이 문제를 풀지 못했다.

따라서 박성원은 그냥 랜덤하게 순열 하나를 정답이라고 출력하려고 한다. 이 문제에는 정답이 여러 개 있을 수도 있고, 박성원이 우연히 문제의 정답을 맞출 수도 있다.

박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 집합의 수의 개수 N이 주어진다. N은 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 집합에 포함된 수가 주어진다. 각 수의 길이는 길어야 50인 자연수이다. 마지막 줄에는 K가 주어진다. K는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다.

예제 입력 1

3
3
2
1
2

예제 출력 1

1/3

예제 입력 2

5
10
100
1000
10000
100000
10

예제 출력 2

1/1

예제 입력 3

5
11
101
1001
10001
100001
10

예제 출력 3

0/1

예제 입력 4

9
13
10129414190271203
102
102666818896
1216
1217
1218
101278001
1000021412678412681
21

예제 출력 4

5183/36288

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: djm03178
  • 빠진 조건을 찾은 사람: djm03178