A sequence \(S\) of length \(N\) is called co-prime sequence if \(GCD(S[i], S[i + 1]) = 1\) for \(0 \le i < N - 1\), i.e. every adjacent element is co-prime, any sequence of length \(1\) is a co-prime sequence.
Given an Array \(arr\) of length \(N\), find the number of non-empty co-prime subsequences of this array, modulo \(10^9+7\).
Input Format:
Output Format:
Constraints: