---

Problem 791

---

Average and Variance

Denote the average of $k$ numbers $x_1, …, x_k$ by $\bar{x} = \frac{1}{k} \sum_i x_i$. Their variance is defined as $\frac{1}{k} \sum_i \left( x_i - \bar{x} \right) ^ 2$.

Let $S(n)$ be the sum of all quadruples of integers $(a,b,c,d)$ satisfying $1 \leq a \leq b \leq c \leq d \leq 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, …, x_k$的均值为$\bar{x} = \frac{1}{k} \sum_i x_i$，并记其方差为$\frac{1}{k} \sum_i \left( x_i - \bar{x} \right) ^ 2$。

考虑所有满足$1 \leq a \leq b \leq c \leq d \leq 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$取余。

---