题目描述

给定一个长度为 $n$ 的序列 $a$，考虑如下过程：

• 初始 $sum=0$。
• 从 $[1,n]$ 中随机选出一个数 $s$，令 $l=s$，$r=s$，$sum=a_s$。
• 重复以下过程 $n-1$ 次：
  • 按以下规则生成一个随机数 $x$：
    • 若 $l=1$，则 $x=1$。
    • 若 $r=n$，则 $x=0$。
    • 否则 $x$ 有 $\frac{1}{2}$ 的概率为 $1$，有 $\frac{1}{2}$ 的概率为 $0$。
  • 若 $x=0$，先令 $l\leftarrow l-1$，再令 $sum\leftarrow sum+a_l\times(r-l+1)$。
  • 若 $x=1$，先令 $r\leftarrow r+1$，再令 $sum\leftarrow sum+a_r\times(r-l+1)$。

可以证明以上过程结束后总有 $l=1$ 且 $r=n$，请你求出以上过程结束后 $sum$ 的期望值，也即 $E(sum)$，你只需要输出这个值对 $666528221$ （一个质数）取模后的值即可。

形式化地说，可以证明 $E(sum)$ 可以被表示成 $\frac{p}{q}$ 的形式，其中 $p,q$ 均为整数且 $\gcd(p,q)=1$ 且 $q\not\equiv0\pmod{666528221}$。可以证明在 $[0,666528221)$ 中唯一存在一个整数 $r$ 满足 $q\times r\equiv p\pmod{666528221}$，你只需要输出这个 $r$ 即可。

输入格式

第一行一个正整数 $n$，表示 $a$ 的长度。

第二行 $n$ 个正整数，表示 $a$。

输出格式

一行一个非负整数，表示答案对 $666528221$ 取模后的值。

2
1 2

333264115

样例解释 1

若 s=0，则 ans=1+22=5。 若 s=1，则 ans=2+12=4。 故 E(ans)=9/2，你可以验证 2*333264115 mod 666528221=9。

3
1 2 3

12

数据范围

对于 $10\%$ 的数据，保证 $n\le 10$。

对于 $30\%$ 的数据，保证 $n\le 500$​。

对于 $50\%$ 的数据，保证 $n\le 5000$。

对于另外 $10\%$ 的数据，保证 $a$ 中所有数均相同。

对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$1\le a_i< 666528221$。