Google | Phone Screen | Subsets LCM

Find the total number of subsets of an array such that the LCM of elements in each subset is divisible by k.

Constraints:
size(arr) ≤ 10^5
1 ≤ arr[i] ≤ 10^9
1 ≤ k ≤ 10^9

Input: arr = {1, 7, 3, 2, 5}, k = 7
Output: 16

Input: arr = {2, 3, 1, 6, 1}, k = 6
Output: 20