1s, 512 MB
You are given a sequence of length .
For an arbitrary number , can be defined as the number of non-empty subsequences of such that each element of , denoted by , is divisible by and .
Compute . As the result can be very large, you should print the value modulo .
- A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
The first line contains a single integer ().
The second line of each test case contains integers ().
Print a single integer — the answer to the problem modulo .
2 1 6 5 8
Let’s look at how is calculated. There are 3 subsequences which satisfy the given conditions: . So, .
And . Hence the answer is