Problem 910

$L$-expressions II

An $L$-expression is defined as any one of the following:

a natural number;
the symbol $A$;
the symbol $Z$;
the symbol $S$;
a pair of $L$-expressions $u, v$, which is written as $u(v)$.

An $L$-expression can be transformed according to the following rules:

$A(x) \to x + 1$ for any natural number $x$;
$Z(u)(v) \to v$ for any $L$-expressions $u, v$;
$S(u)(v)(w) \to v(u(v)(w))$ for any $L$-expressions $u, v, w$.

For example, after applying all possible rules, the $L$-expression $S(Z)(A)(0)$ is transformed to the number $1$:
$$S(Z)(A)(0) \to A(Z(A)(0)) \to A(0) \to 1.$$
Similarly, the $L$-expression $S(S)(S(S))(S(Z))(A)(0)$ is transformed to the number $6$ after applying all possible rules.

Define the following $L$-expressions:

$C_0 = Z$;
$C_i = S(C_{i - 1})$ for $i \ge 1$;
$D_i = C_i(S)(S)$.

For natural numbers $a, b, c, d, e$, let $F(a, b, c, d, e)$ denote the result of the $L$-expression $D_a(D_b)(D_c)(C_d)(A)(e)$ after applying all possible rules.

Find the last nine digits of $F(12, 345678, 9012345, 678, 90)$.

Note: it can be proved that the $L$-expression in question can only be transformed a finite number of times, and the final result does not depend on the order of the transformations.

$L$-表达式（二）

一条$L$-表达式可以是以下任意一种：

一个自然数；
符号$A$；
符号$Z$；
符号$S$；
一对$L$-表达式$u, v$，并记作$u(v)$。

$L$-表达式可以按照以下规则进行转换：

对任意自然数$x$，$A(x) \to x + 1$；
对任意$L$-表达式$u, v$，$Z(u)(v) \to v$；
对任意$L$-表达式$u, v, w$，$S(u)(v)(w) \to v(u(v)(w))$。

例如，在应用所有可能的规则后，$L$-表达式$S(Z)(A)(0)$可以被转换为数$1$：
$$S(Z)(A)(0) \to A(Z(A)(0)) \to A(0) \to 1.$$
类似地，$L$-表达式$S(S)(S(S))(S(Z))(A)(0)$在应用所有可能的规则后被转换为数$6$。

定义如下的$L$-表达式：

$C_0 = Z$;
$C_i = S(C_{i - 1})$ for $i \ge 1$;
$D_i = C_i(S)(S)$.

对于自然数$a, b, c, d, e$，令$F(a, b, c, d, e)$表示表达式$D_a(D_b)(D_c)(C_d)(A)(e)$在应用所有可能的规则后得到的结果。

求$F(12, 345678, 9012345, 678, 90)$的最后九位数字。

注意：可以证明，本题所涉及的$L$-表达式只能被应用有限次转换，且最终结果不依赖于转换的顺序。