Today, Yuta gives Rikka a simple math task: given a positive integer array A of length n and a positive integer m, does the equation ≡0modm equiv 0 mod m≡0modm have any solutions?
Today, Yuta gives Rikka a simple math task: given a positive integer array A of length n and a positive integer m, does the equation (∑i=1nAixi)≡0mod m(sum_{i=1}^n A_ix_i) equiv 0 mod m(∑i=1nAixi)≡0modm have any solutions? Rikka solves this problem easily: ∀i∈[1,n],xi=0forall i in [1,n], x_i =0∀i∈[1,n],xi=0 is always a solution of this equation. And then, Yuta shows a much harder version of this task: For a positive integer array A of length n and a positive integer m, let f(A,m) be the number of different integer vectors x which satisfy xi ∈ [0,m) and (∑i=1nAixi)≡0mod m(sum_{i=1}^n A_ix_i) equiv 0 mod m(∑i=1nAixi)≡0modm. For example, when A=[1,1], m=2, there are 2 integer vectors [0,0],[1,1] satisfy the previous conditions. So f([1,1],2) is equal to 2. Now Yuta shows a positive integer array B of length n and a positive integer M. B has N=2n-1 non-empty subsequences A1,...,AN. For each integer m ∈ [1,M], Yuta wants to know ∑i=1Nf(Ai,m)sum_{i=1}^N f(A_i, m)∑i=1Nf(Ai,m). For example, when B=[1,1] and M = 3, Rikka needs to calculate f([1],1) x 2 + f([1,1],1), f([1],2) x 2 + f([1,1],2) and f([1],3) x 2 + f([1,1],3). This task is too hard for Rikka. So she wants you to help her.
