The ghost exploration team find some 1D coordinate where the cursed object is located. You will be given such cursed positions. All the locations are integers. You need to find the possible ghost spawning area using those cursed object positions.
The ghost has a special affection for numbers to . An area is said to be a ghost spawning area if it is divisible by all the numbers from to .
Being a member of the ghost exploration team, you need to find out the number of ways of selecting one or more cursed object locations from those locations such that the product of those locations returns a ghost spawning area.
Since the answer can be very big, output the answer modulo .
The first line of input is an integer . The next line will contain different integer numbers.
Print the number of ways of selecting one or more cursed object locations modulo such that the product of those locations becomes a ghost spawning area.
Input | Output |
---|---|
7 1 2 3 4 5 6 7 | 4 |
Input | Output |
---|---|
6 1 2 3 4 5 6 | 0 |