박성원의 확률

서로 다른 양의 정수 N개로 이루어진 집합이 있다. 이 정수들을 어떤 순서로 모두 이어 붙이면 하나의 큰 정수가 된다. 예를 들어 {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을 출력한다.