algorithm - 所有子集的乘积之和，

我要计算给定$n$元素集的每个子集的乘积之和。例如，给定集合{1，2，3}，答案是1+2+3+1*2+1*3+2*3+1*2*3我还想给出模M$的答案。
我知道的是我可以计算$（x-a-u 1）（x-a-u 2）…（x-a-u n）-1$，但是这需要FFT，所以可能会有一些舍入误差，但是这个想法的主要问题是它需要$O（n-log^2 n）$时间，做模M$是有问题的有没有更快的方法来解决这个问题？这不是我的家庭作业，我从老师那里得到了这个任务来练习编程比赛，但我真的被这个问题困住了。
限制条件：
10^9美元$
10^6美元$
10^9美元$

最佳答案

所讨论的总数是

[(1+a_1)*(1+a_2)*(1+a_3)*...*(1+a_N) - 1] (mod M)

这是

[(1+a_1)%M * (1+a_2)%M * ... * (1+a_N)%M - 1] % M

如果你能做得更好，我会很惊讶的。
下面是一个python实现：

def sumProducts(nums, M):
    p = 1
    for num in nums:
        p = p*((1+num)%M)%M
        if p == 0:
            return M-1
    return (p-1)%M

我在上面给出的原始公式中进行的优化是取每个新因子的乘积模，如果遇到零，则使乘积短路——如果在(1 + a_i)中出现素数因子（根据多重性计数），则会发生这种情况
一个简单的测试：

>>> sumProducts([1,2,3],5)
3

这很容易用手验证。
压力测试：

>>> from random import randint
>>> nums = [randint(1,1000000) for i in range(100000)]

nums是100万个介于1到100万之间的随机数
当然，

>>> sumProducts(nums,2**32)
4294967295

因为nums中至少有32个奇数（因此32个数a_i为偶数）。
另一方面，10000003是大于1000000的质数，因此计算不会短路：

>>> sumProducts(nums,1000003)
719694

计算时间不到一秒钟。