Sum of Beauty of Increasing Subsequences

Problem Statement

Sum of Beauty of Increasing Subsequences Problem Description You are given an array A of length N. We define beauty(g) as g multiplied by the number of strictly increasing subsequence of A, where the GCD (greatest common divisor) of all the elements in any of these sequences is exactly g. Find the sum of beauty(g) for all positive integers (greater than zero). Since the answer can be very large, return it modulo 10^9 + 7. The input format is as follows: The first line contains an integer, N, denoting the number of elements in A. Each line i of the N subsequent lines (where 0 <= i < N) contains an integer describing A[i]. Examples Example 1: Input: 1 1 Output: 1 Explanation: N=1, A=[1]. The only increasing subsequence is [1] with gcd equal to 1 so the answer is 1 * 1 = 1. Example 2: Input: 2 2 2 Output: 4 Explanation: N=2, A=[2 2]. There are two increasing sequences: [2] and [2] (first and second index), and both of gcd 2 so the answer is 2 * 2 = 4. Example 3: Input: 3 2 1 2 Outpu