Park Seongwon's Probability

Interview

Time limit2sMemory limit128 MB

Summary

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

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics, Number theory
Solved: No attempts yet

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.

Examples4

Example 1
Input
```
3
3
2
1
2
```
Expected output
```
1/3
```
Example 2
Input
```
5
10
100
1000
10000
100000
10
```
Expected output
```
1/1
```
Example 3
Input
```
5
11
101
1001
10001
100001
10
```
Expected output
```
0/1
```

Example 4

Input

9
13
10129414190271203
102
102666818896
1216
1217
1218
101278001
1000021412678412681
21

Expected output

5183/36288