Great Subsequences

A non-empty subsequence is good if the GCD of all its elements is greater than 1. Perform the point replacements one by one; after each one, take the number of good subsequences modulo 10⁹+7, and finally add these reduced counts together directly. The final sum is not taken modulo. Choices of different indices are counted separately.

输入格式

The first line contains N Q (1..100000), and the second line contains N values of A (1..100000); then Q lines X Y follow, with 1≤X≤N and 1≤Y≤100000.

输出格式

Output a single integer, the answer.

样例 1

输入：

2 1
1 2
1 2

输出：

3

样例 2

输入：

3 2
1 2 3
1 3
2 3

输出：

11

样例 3

输入：

5 2
2 2 2 2 2
1 1
2 1

输出：

22

样例说明

Example 1: the array becomes 2, 2; both single elements and the pair are valid, for 3 in total.

Example 2: after the two replacements there are 4 and 7 good subsequences respectively, for a sum of 11.

Example 3: the two replacements leave 4 copies of 2 and 3 copies of 2, giving 15 and 7 respectively, for a sum of 22.