数学推导
首先不难得到：
\[\begin{aligned} f(n)&=\sum_{i=0}^nx^i\\ &=\dfrac{x^{n+1}-1}{x-1} \end{aligned}\]因为 $\operatorname{lcm}\left(\dfrac ac,\dfrac bc\right)=\dfrac{\operatorname{lcm}(a,b)}{c}$，因此定义 $g(n)=(x-1)f(n)=x^{n+1}-1$，有：
\[\begin{aligned} \operatorname*{lcm}_{i=1}^nf(a_i)=\dfrac{\displaystyle\operatorname*{lcm}_{i=1}^ng(a_i)}{x-1} \end{aligned}\]考虑如何求 $\displaystyle\operatorname*{lcm}_{i=1}^ng(a_i)$。
根据 gcd-lcm 容斥：
\[\operatorname*{lcm}_{i\in T}i=\prod_{S\subseteq T}\left(\gcd_{i\in S}i\right)^{(-1)^{\vert S\vert-1}}\]因此，记 $T=\set{1,2,3,\cdots,n}$，有：
\(\operatorname*{lcm}_{i\in T}g(a_i)=\prod_{S\subseteq T}\left(\gcd_{i\in S}g(a_i)\right)^{(-1)^{\vert S\vert-1}}\) 考虑如何将 $\gcd\limits_{i\in S}g(a_i)$ 转化。
注意到 $g(a_i)=x^{a_i+1}-1$，并且 $\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1$。
因为：
\[\begin{aligned} \gcd(x^a-1,x^b-1)&=\gcd(x^a-1-x^{a-b}(x^b-1),x^b-1)\\ &=\gcd(x^{a-b}-1,x^b-1) \end{aligned}\]容易发现指数可以进行辗转相减，因此有 $\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1$。
故，有：
\(\begin{aligned} \operatorname*{lcm}_{i\in T}g(a_i)&=\prod_{S\subseteq T}\left(\gcd_{i\in S}\left(x^{a_i+1}-1\right)\right)^{(-1)^{\vert S\vert-1}}\\ &=\prod_{S\subseteq T}\left(x^{\gcd\limits_{i\in S}(a_i+1)}-1\right)^{(-1)^{\vert S\vert-1}}\\ \end{aligned}\) 朴素求解是 $\mathcal O\left(n2^n\right)$ 的，不能接受。考虑 DP 求解。
DP 求解
发现答案与且仅与 $\gcd\limits_{i\in S}(a_i+1),T$ 和 $\vert S\vert$ 的奇偶性相关，考虑将其设计入 DP 状态。
设 $\textit{dp}{i,j,k}$ 表示 $T=\set{1,2,3,\cdots,i},\gcd\limits{i\in S}(a_i+1)=j,\vert S\vert\bmod 2=k$ 的出现次数。（且 $i\in S$ 必然成立，否则等效于 $\textit{dp}_{i-1,j,k}$）
需要注意的是，总状态量是可以接受的，因为 $j$ 是某个 $a_l+1$ 的因数，$k\in\set{0,1}$。因为当 $n\leq10^9$ 时，$d(n)\leq1344$，其中 $d(n)$ 表示 $n$ 的因数个数。总状态量只有 $\mathcal O(nd(V))$ 个。
需要先继承上一轮的状态：
\[\textit{dp}_{i,j,k}\leftarrow\textit{dp}_{i-1,j,k}\]不难得到进一步转移：
\[\textit{dp}_{i,\gcd(j,a_i+1),k+1}\leftarrow\textit{dp}_{i,\gcd(j,a_i+1),(k+1)\bmod 2}+\textit{dp}_{i,j,k}\]初始边界有：
\[\textit{dp}_{0,0,0}=1\]但是需要注意这仅仅是为了便于运算而产生的，无实际意义。统计答案时也要跳过。
最终答案即： \(\prod_{j,k}\left(\left(x^j-1\right)^{(-1)^{k-1}}\right)^{\textit{dp}_{n,j,k}}\) 即所有合法的 $j,k$ 的 $\left(\left(x^j-1\right)^{(-1)^{k-1}}\right)^{\textit{dp}_{n,j,k}}$ 之积。
时间复杂度：$\mathcal O(nd(V)\log V+d(V)\log P)$。$\mathcal O(1)$ 转移，因为求 $\gcd$ 和快速幂，会有 $\mathcal O(\log V)$ 或 $\mathcal O(\log P)$ 的复杂度。
空间复杂度：滚动数组可以做到 $\mathcal O(d(V))$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
typedef long long ll;
constexpr const int N=100,P=1e9+7;
int n,x,a[N+1];
struct cmp{
int operator ()(pair<int,int> x)const{
return hash<int>()(x.first)^hash<int>()(x.second);
}
};
__gnu_pbds::gp_hash_table<pair<int,int>,int,cmp>dp,backup;
inline int qpow(int base,int n){
n%=P-1;
if(n<0){
n+=P-1;
}
int ans=1;
while(n){
if(n&1){
ans=1ll*ans*base%P;
}
base=1ll*base*base%P;
n>>=1;
}
return ans;
}
inline int gcd(int a,int b){
while(b){
int tmp=a;
a=b;
b=tmp%b;
}
return a;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll pl;
cin>>pl>>n;
x=pl%P;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[{0,0}]=1;
for(int i=1;i<=n;i++){
backup=dp;
for(auto &pl:backup){
auto &state=pl.first;
int &value=pl.second;
auto &p=dp[{gcd(state.first,a[i]+1),state.second^1}];
p=(p+value)%P;
}
}
int ans=qpow(x-1,P-2);
for(auto &pl:dp){
auto &state=pl.first;
int &value=pl.second;
if(!state.first){
continue;
}
switch(state.second&1){
case 0:
ans=1ll*ans*qpow(qpow(x,state.first)-1,-value)%P;
break;
case 1:
ans=1ll*ans*qpow(qpow(x,state.first)-1,value)%P;
break;
}
}
if(ans<0){
ans+=P;
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
