　$n=2^{2020}$ とする. 総和が奇数の条件を無視すれば ${\_{4n}}\mathrm{C}\_{2n}$ 通りである. このうち, すべてが偶数かつ $a_{2i-1}=a_{2i}$ をみたすもの ${\_{2n}}\mathrm{C}\_{n}$ 通りを除き, 総和が偶数のものと奇数のものが一対一に対応することを確認しよう. 実際に, 条件「$a_{2i-1}=a_{2i}$ かつこれらが偶数である」をみたさない最小の $i$ をとれば, 以下のように対応が得られる.

- $a_{2i-1}$ が奇数のとき, $a_{2i-1} \longmapsto a_{2k-1}-1$
- $a_{2i-1}$ が偶数のとき, $a_{2i-1} \longmapsto a_{2k-1}+1$

　以下, 一般に $\dbinom{2^{m+1}}{2^m}-\dbinom{2^m}{2^{m-1}}$ が $2$ でちょうど $3m$ 回割り切れることを示せば, 求める値は $\textbf{6062}$ となることがわかる. すなわち, 示すべきことは
$$\dbinom{2^{m+1}}{2^m}-\dbinom{2^m}{2^{m-1}}\equiv2^{3m}\pmod{2^{3m+1}}$$
ここで $x_i=2i-1$ およびその積 $X=x_1x_2\cdots x_{2^{m-1}}$ について, $2^{2m-1}$ を法として
$$
\begin{aligned}
\displaystyle\sum_{i=1}^{2^{m-1}}\dfrac{X}{x_i}&=\dfrac{1}{2} \Biggl(\displaystyle\sum_{i=1}^{2^{m-1}}\dfrac{X}{x_i}+\dfrac{X}{x_{2^{m-1}-i+1}}\Biggr) \\\\
&=2^{m-1}\displaystyle\sum_{i=1}^{2^{m-1}}\dfrac{X}{x_ix_{2^{m-1}-i+1}}\\\\
&\equiv -2^{m-1}X\sum_{i=1}^{2^{m-1}}(x_i^{-1})^2 \\\\
&\equiv -2^{m-1}X \sum_{i=1}^{2^{m-1}}x_i^2 \\\\
&\equiv -2^{m-1}X\times\dfrac{2^{m-1}(2^m-1)(2^m+1)}{3} \\\\
&\equiv 2^{2m-2}\times\text{奇数} \\\\
&\equiv 2^{2m-2}
\end{aligned}
$$
これを利用すると
$$\displaystyle2\times\Biggl(\prod_{i=1}^{2^{m-1}}(2^m+x_i)-\prod_{i=1}^{2^{m-1}}(2^m-x_i)\Biggr)\equiv 2^{3m}\pmod{2^{3m+1}}$$
一方で $\displaystyle\prod_{i=1}^k(2^i-1)!!=A_k$ とすると, $(2^k)!=2^{2^k-1}\times A_k$ であるから
$$\dbinom{2^{m+1}}{2^m}-\dbinom{2^m}{2^{m-1}}=2\times(2^m-1)!!\times\dfrac{\displaystyle\prod_{i=1}^{2^{m-1}}(2^m+x_i)-\prod_{i=1}^{2^{m-1}}(2^m-x_i)}{A_m}$$
以上より所望の結論を得る.
公式解説
https://onlinemathcontest.com/contests/omckoukou2/editorial/2205
　$M$ を求めるお話です．FPS (形式的冪級数) が使えそうだったので使いました．

----

　まず，$M$ は以下で表される式を展開したときの $x^{2^{2021}}y^{奇数}$ の係数の総和に等しい（※）．
$$f(x,y)=(1+x+x^2+\cdots)(1+xy + x^2y^2+\cdots)(1+xy^2 + x^2y^4 + \cdots)\cdots(1+xy^{2^{2021}}+x^2y^{2\times 2^{2021}}+\cdots)$$
さらに，実際に展開した後の様子を考えれば，これは $(f(x,1)-f(x,-1))\/2$ の $x^{2^{2021}}$ の係数に等しい．以下これを求める．
- $f(x,1)$ について．
$$f(x,1)=(1+x+x^2+\cdots)^{2^{2021}+1}$$
の $x^{2^{2021}}$ の係数を考えればよく，これは「 $2^{2021}+1$ 個の順序付いた非負整数の組であって，その総和が $2^{2021}$ であるものの総数」と等しいことから ${}\_{2^{2022}} \mathrm{C}\_{2^{2021}}$ と求められる．


- $f(x,-1)$ について．
$$f(x,y)=\frac{1}{1-x}\times \frac{1}{1-xy} \times \cdots \frac{1}{1-xy^{2^{2021}}}$$
より，特に
$$f(x,-1)=\left(\frac{1}{1-x}\times \frac{1}{1+x}\right)^{2^{2020}+1}(1+x) = (1+x^2+x^4+\cdots)^{2^{2020}+1}(1+x)$$
つまり $(1+x^2+x^4+\cdots)^{2^{2020}+1}$ の $x^{2^{2021}}$ の係数を考えればよいから，これは先ほどと同様に ${}\_{2^{2021}} \mathrm{C}\_{2^{2020}}$ と求められる．

以上より，
$$M=\frac{f(x,1)-f(x,-1)}{2} = \frac{{}\_{2^{2022}} \mathrm{C}\_{2^{2021}} - {}\_{2^{2021}} \mathrm{C}\_{2^{2020}}}{2}$$
と求められた．

----

（※）\
　各因子は左から順番に $0$ の個数とその総和への寄与， $1$ の個数とその総和への寄与，... を意味しています．ここで，$y$ は $a_1+a_2+\cdots$ に対応します．本問では「$2^{2021}$ 個の非負整数」の和が奇数となる場合の数を求めるので，文字 $x$ を導入し，$\underline{{x^{2^{2021}}}} y^{奇数}$ の係数，という縛りを設けて対応しています．\
　また，実際にはある数が $a_1, a_2, \cdots, a_{2^{2021}}$の中に $2^{2021}$ 個以上含まれることはないため，各因子は無限次にならないのでは？という疑問があるかもしれませんが，最終的に見るのは $x^{2^{2021}}y^{奇数}$ の係数のみなので無限次にしたところで答えには影響しません．\
　この式の立て方は [PCT 氏](https:\/\/onlinemathcontest.com\/users\/PCTprobability)の [Mathlog の記事](https:\/\/mathlog.info\/articles\/229)を参考にしました．
ユーザー解説
https://onlinemathcontest.com/contests/omckoukou2/editorial/2205/114
　総和が奇数である整数の組 $0\leq a_1\leq a_2\leq\cdots\leq a_{2^{2021}}\leq 2^{2021}$ は $M$ 通りあります. $M$ が $2$ で割り切れる最大の回数を求めてください.