cho.sh

Park Seongwon's Probability

Count permutations of up to 15 numbers whose concatenation is divisible by K, and output the probability as a reduced fraction.

Medium6Dynamic programmingBit manipulationCombinatoricsNumber theoryInterviewNo attempts yetTime limit2sMemory limit128 MB

Problem

There is a set of N distinct positive integers. If all of these integers are concatenated in some order, they form one large integer. For example, concatenating {5221, 40, 1, 58, 9} in that order gives 5221401589.

Park Seongwon chooses one permutation of the integers uniformly at random and treats it as the answer. A permutation is correct if the concatenated integer is divisible by K.

Find the probability that Park Seongwon accidentally chooses a correct permutation, written as a reduced fraction.

Input

The first line contains the number N of integers in the set. N is a positive integer no greater than 15.

Each of the next N lines contains one integer from the set. Each integer is positive and has length at most 50.

The last line contains a positive integer K. K is no greater than 100.

Output

Print the answer as a reduced fraction in the form p/q, where p is the numerator and q is the denominator. If the probability is 0, print 0/1. If the probability is 1, print 1/1.