这不傻逼题吗(Hard)

这道题和另一题内容一样，仅仅是数据范围不同。

Xenny去参加概率论的期末考试，因为老师说全是单选题，每道题有A_i个选项，Xenny相信自己运气很好，所以Xenny的答案能够全部蒙对，但是填选项的时候却把第i道题的答案填到了第i+1道题的位置，而且还将第n道题填到了第1道题上。现在Xenny想让你帮忙算算做对题目的期望数。
因为输入很大，避免读入耗时，其实是输入文件太大了 ==，a[]数组请用下面程序生成

for (int i=2; i <= n; i++) {
    a[i] = ((long long)a[i-1]*A+B)%100000001;
}
for (int i = 1; i <= n; i++) {
    a[i] = a[i]%C+1;
}

单组数据。
第一行一个整数n(0<n<=10000000)——代表题目的个数。
第二行四个整数A,B,C,A₁(0<=A,B,C,A₁<=100000000)——代表生成输入函数的参数

输出期望做对的题目个数，答案保留三位小数。

3
2 0 4 1

1.167

A[] = {2,3,1}
正确答案   |   Xenny的答案   | 做对题目| 出现概率
{1,1,1}    |    {1,1,1}    |    3    |    1/6
{1,2,1}    |    {1,1,2}    |    1    |    1/6
{1,3,1}    |    {1,1,3}    |    1    |    1/6
{2,1,1}    |    {1,2,1}    |    1    |    1/6
{2,2,1}    |    {1,2,2}    |    1    |    1/6
{2,3,1}    |    {1,2,3}    |    0    |    1/6