---

Problem 791

---

Average and Variance

Denote the average of $k$ numbers $x_1,\dots ,x_k$ by $\overline{x}=\frac{1}{k}\sum _i{x}_i$. Their variance is defined as $\frac{1}{k}\sum _i{(x_i-\overline{x})}^2$.

Let $S(n)$ be the sum of all quadruples of integers $(a,b,c,d)$ satisfying $1\le a\le b\le c\le d\le n$ such that their average is exactly twice their variance.

For $n=5$, there are $5$ such quadruples, namely: $(1,1,1,3),(1,1,3,3),(1,2,3,4),(1,3,4,4),(2,2,3,5)$.

Hence $S(5)=48$. You are also given $S({10}^3)=37048340$.

Find $S({10}^8)$. Give your answer modulo $433494437$.

---

均值与方差

记$k$个数$x_1,\dots ,x_k$的均值为$\overline{x}=\frac{1}{k}\sum _i{x}_i$，并记其方差为$\frac{1}{k}\sum _i{(x_i-\overline{x})}^2$。

考虑所有满足$1\le a\le b\le c\le d\le n$的整数四元组$(a,b,c,d)$，记$S(n)$为其中均值恰好为方差两倍的四元组之和。

对于$n=5$，共有$5$个满足上述条件的四元组，分别是$(1,1,1,3),(1,1,3,3),(1,2,3,4),(1,3,4,4),(2,2,3,5)$。

因此，$S(5)=48$。已知$S({10}^3)=37048340$。

求$S({10}^8)$，并将你的答案对$433494437$取余。

---