A sequence S of length N is called co-prime sequence if GCD(S[i],S[i+1])=1 for 0≤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 109+7.
Input Format:
Output Format:
Constraints: