首先考虑如何快速计算自乘:即

能用快速幂维护(欧拉定理).
然后考虑用log代表原始数的关系,发现一层log不太够用,还是会出现倍增的形式,那么就两层log,这个时候自乘变为 $k\log 2+\log\log n$ ,初始时不太规律,后面就会出现一个数当前比所有数都小,然后自乘之后比所有数都大的局面(周期性),所以只需要暴力维护3n以前的自乘,中间的直接整除算出来,最后的数字因为不整,也暴力算.
exp:

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
fastio::IN fin;
fastio::OUT fout;
template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
	T1 res(1);
	while(po>0){
		if(po&1)
			res=res*b%p;
		b=b*b%p;
		po>>=1;
	}
	return res;
}
const int mod=1234567891;
const int phi=1234567890;

i64 dat[10000];
long double lgg[10000];
i64 pp[10000];

i64 del=1e16;
i64 n=1e4;

i64 res;
int main(){
	for(int i=1;i<n;++i){
		dat[i]=i+1;
		lgg[i]=log10(log10((long double)dat[i]));
	}
	n--;
	const long double l2=log10((long double)2);
	priority_queue<pair<long double,i64>,vector<pair<long double,i64>>,greater<pair<long double,i64>>> pq;
	for(int i=1;i<=n;++i){
		pq.push({lgg[i],i});
	}
	for(int i=1;i<=3*n;++i){
		auto x=pq.top();pq.pop();
		pp[x.second]++;
		pq.push({x.first+l2,x.second});
	}
	del-=3*n;
	i64 rou=del/n;
	del-=rou*n;
	for(int i=1;i<=n;++i){
		pp[i]+=rou;
	}
	for(int i=1;i<=del;++i){
		auto x=pq.top();
		pq.pop();
		pp[x.second]++;
		pq.push({x.first+l2,x.second});
	}
	i64 cnt=0;
	for(int i=1;i<=n;++i){
		res=(res+qp(dat[i],qp((i64)2,pp[i],phi),mod))%mod;
		cnt+=pp[i];
	}
	fout<<res<<" "<<cnt;
	return 0;
}