Problem 941
de Bruijn’s Combination Lock
de Bruijn has a digital combination lock with $k$ buttons numbered $0$ to $k-1$ where $k \le 10$.
The lock opens when the last $n$ buttons pressed match the preset combination.
Unfortunately he has forgotten the combination. He creates a sequence of these digits which contains every possible combination of length $n$. Then by pressing the buttons in this order he is sure to open the lock.
Consider all sequences of shortest possible length that contains every possible combination of the digits.
Denote by $C(k, n)$ the lexicographically smallest of these.
For example, $C(3,2)=0010211220$.
Define the sequence $a_n$ by $a_0=0$ and
$$a_n=(920461 a_{n-1}+800217387569)\bmod 10^{12} \text{ for }\ n > 0$$
Interpret each $a_n$ as a $12$-digit combination, adding leading zeros for any $a_n$ with less than $12$ digits.
Given a positive integer $N$, we are interested in the order the combinations $a_1,\dots,a_N$ appear in $C(10,12)$.
Denote by $p_n$ the place, numbered $1,\dots,N$, in which $a_n$ appears out of $a_1,\dots,a_N$. Define $\displaystyle F(N)=\sum_{n=1}^Np_na_n$.
For example, the combination $a_1=800217387569$ is entered before $a_2=696996536878$. Therefore:
$$F(2)=1\cdot800217387569 + 2\cdot696996536878 = 2194210461325$$
You are also given $F(10)=32698850376317$.
Find $F(10^7)$. Give your answer modulo $1234567891$.
德布鲁因的组合锁
德布鲁因有一个数字组合锁，锁上有$k$个按钮，编号从$0$到$k-1$，其中$k \le 10$。
只有最后按下的$n$个按钮与预设的密码组合相匹配时，锁才会被打开。
不巧的是，他忘记了密码组合。相反，他构造了一个包含所有长度为$n$的密码组合的数字序列，只需按照这个序列按下按钮，他确信能够打开锁。
考虑所有包含全部密码组合且长度最短的序列。
用$C(k, n)$表示这些序列中字典序最小的一个。
例如，$C(3, 2) = 0010211220$。
定义序列$a_n$，其中$a_0=0$且
$$a_n=(920461 a_{n-1}+800217387569)\bmod 10^{12} \text{ for }\ n > 0$$
每个$a_n$可以视为一个$12$位数字的密码组合，若$a_n$少于$12$位数字则添加前导零。
给定正整数$N$，我们感兴趣的是密码组合$a_1,\dots,a_N$在$C(10,12)$中出现的顺序。
记$a_n$在$a_1,\dots,a_N$中出现的顺序或位置为$p_n$，也即$p_n$的取值为$1,\dots,N$。定义$\displaystyle F(N)=\sum_{n=1}^Np_na_n$。
例如，密码组合$a_1=800217387569$在$a_2=696996536878$之前出现，因此：
$$F(2)=1\cdot800217387569 + 2\cdot696996536878 = 2194210461325$$
已知$F(10)=32698850376317$。
求$F(10^7)$，并对$1234567891$取余作为你的答案。