Problem 937

Equiproduct Partition

Let $\theta=\sqrt{-2}$.

Define $T$ to be the set of numbers of the form $a+b\theta$, where $a$ and $b$ are integers and either $a\gt 0$, or $a=0$ and $b\gt 0$. For a set $S \subseteq T$ and element $z \in T$, define $p(S,z)$ to be the number of ways of choosing two distinct elements from $S$ with product either $z$ or $-z$.

For example if $S=\{1,2,4\}$ and $z=4$, there is only one valid pair of elements with product $\pm4$, namely $1$ and $4$. Thus, in this case $p(S,z)=1$.

For another example, if $S=\{1,\theta,1+\theta,2-\theta\}$ and $z=2-\theta$, we have $1\cdot(2-\theta)=z$ and $\theta\cdot(1+\theta)=-z$, giving $p(S,z)=2$.

Let $A$ and $B$ be two sets satisfying the following conditions:

$1 \in A$
$A \cap B = \emptyset$
$A \cup B = T$
$p(A,z) = p(B,z)$ for all $z\in T$

Remarkably, these four conditions uniquely determine the sets $A$ and $B$.

Let $F_n$ be the set of the first $n$ factorials: $F_n=\{1!,2!,\dots,n!\}$, and define $G(n)$ to be the sum of all elements of $F_n\cap A$.

You are given $G(4) = 25$, $G(7) = 745$, and $G(100) \equiv 709772949 \pmod{10^9+7}$.

Find $G(10^8)$ and give your answer modulo $10^9+7$.

等积划分

令$\theta=\sqrt{-2}$。

定义$T$为形如$a+b\theta$的数所构成的集合，其中$a$和$b$均为整数，且满足$a\gt 0$，或$a=0$且$b\gt 0$。对于集合$S \subseteq T$和元素$z \in T$，定义$p(S,z)$为从$S$中选择两个不同元素且它们的乘积为$z$或$-z$的方法数。

例如，如果$S=\{1,2,4\}$且$z=4$，只有一个合法元素对（$1$和$4$）的乘积为$\pm4$，因此$p(S,z)=1$。

再例如，如果$S=\{1,\theta,1+\theta,2-\theta\}$且$z=2-\theta$，则有$1\cdot(2-\theta)=z$和$\theta\cdot(1+\theta)=-z$，因此$p(S,z)=2$。

记$A$和$B$是满足以下条件的两个集合：

$1 \in A$
$A \cap B = \emptyset$
$A \cup B = T$
对于所有$z\in T$，有$p(A,z) = p(B,z)$

值得注意的是，这四个条件唯一确定了集合$A$和$B$。

令$F_n$为前$n$个阶乘的集合：$F_n=\{1!,2!,\dots,n!\}$，并定义$G(n)$为$F_n\cap A$中所有元素的和。

已知$G(4) = 25$，$G(7) = 745$，以及$G(100) \equiv 709772949 \pmod{10^9+7}$。

求$G(10^8)$，并对$10^9+7$取余作为你的答案。