OMC051(F)

点数: 700

Writer: rusa

　$S = \{0, 1, 2, \ldots,10^{2021}-1\}$ とし，$S$ の部分集合 $\{a_1, a_2, \ldots, a_n\}$ に対しそのスコアを以下で定めます： $$2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$$ 　以下の条件をみたす $S$ の部分集合 $X$ であって，そのスコアが最大になるものは一意に存在することが保証されます．その元の個数を素数 $1009$ で割った余りを求めてください．

• 任意の $a,b \in X$ に対して，$a,b$ の十進法表記で各桁を比較すると，ちょうど $2020$ ヵ所が一致することはない．

　ただし, 上の条件において $a,b$ が十進法表記で $2021$ 桁に満たない場合は，例えば $1$ ならば $000 \cdots 001$ のように，先頭に $0$ を適当に補うことで $2021$ 桁の数とみなして考えるものとします．