# 题目描述

「James Eugene Raynor」让「Space Construction Vehicle」建造了一个煎饼摊，在「Hyperion」号上兜售煎饼，并投放广告：“再给我两根葱，让我把记忆煎成饼”。

和地球上的煎饼果子不同，为了迎合各种船员的口味，「Raynor」准备了 $n$ 种配料，并按添加时间 从后到先 分别编号为 $1,2,⋯,n$，第 $i$ 中配料每份价格是 $P_i$ 元。已知不添加任何配料的煎饼售价为 $6$ 元，每种配料最多只添加一份。

在做一套煎饼时，「Raynor」可以选择一些配料添加到煎饼中，不过，每当添加一份配料，「Raynor」还会额外收取一部分钱当燃料费。具体地，在制作一套煎饼时，如果在所有添加的配料中，配料 $i$ 是倒数第 $j$ 份被添加到煎饼里的配料，那么「Raynor」对这份配料会收取 $P_i×j$ 元的费用。

现在你让「Raynor」将所有可能的搭配都制作了一遍，请你算算你需要支付多少元。由于这个数可能太大，你只需要输出它模 $998244853$ 的余数即可。

# 输入格式

第一行，一个正整数 $n(n≤10^6)$，代表配料种数；

第二行，$n$ 个由空格分开的正整数 $P_i(P_i≤100)$，含义如题目所示。

# 输出格式

一行，一个正整数，代表你需要支付的价钱取模后的余数。

# 样例输入

2

3 4

# 样例输出

42

# 样例解释

总共有 $4$ 种煎饼，分别是不添加配料、添加配料 $1$、添加配料 $2$ 和添加全部配料的。

• 不添加配料：底价 $6$ 元，不加价，价格为 $6$ 元；

• 添加配料 $1$：底价 $6$ 元，配料 $1$ 倒数第一个加入，收取 $3×1=3$ 元，总价格为 $9$ 元；

• 添加配料 $2$：底价 $6$ 元，配料 $2$ 倒数第一个加入，收取 $4×1=4$ 元，总价格为 $10$ 元；

• 添加全部配料：底价 $6$ 元，配料 $1$ 倒数第一个加入，收取 $3×1=3$ 元，配料 $2$ 倒数第二个加入，收取 $4×2=8$ 元，总价格为 $17$ 元。

因此你需要支付 $6+9+10+17=42$ 元。

# 提示

$$\sum_{i = 1}^n i C_{n - 1}^{i - 1} = (n + 1)2^{n - 2}$$

# 题解：组合数学

这道题我们分别考虑每种配料的所有价格加起来，对于第 $i$ 中配料，它可能成为倒数第 $1, 2, \cdots, i$ 个被加入的配料，则：

$$\begin {aligned} c_i & = p_i (1 C_{i - 1}^0 2^{n - i} + 2 C_{i - 1}^1 2^{n - i} + \cdots + i C_{i - 1}^{i - 1} 2^{n - i}) \\ & = p_i \times 2^{n - i} \sum_{j = 1}^i j C_{i - 1}^{j - 1} \\ & = p_i \times 2^{n - i} \times (i + 1) 2^{i - 2} \end {aligned}$$

根据以上公式，只要我们预处理出 $n$ 以内的 $2$ 的次幂，就可以线性累加所有 $c_i$ 得到答案。

时间复杂度：$O(n)$。

参考代码：

#include <stdio.h>

#define MOD 998244853

int n, sum, p[1000010], power[1000010];

int main()

{

    // freopen("V.in", "r", stdin);

    // freopen("V.out", "w", stdout);

    scanf("%d", &n);

    for (int i = 1; i <= n; ++ i)

        scanf("%d", &p[i]);

    power[0] = 1;

    for (int i = 1; i <= n; ++ i)

        power[i] = 1ll * power[i - 1] * 2 % MOD;

    sum = 6ll * power[n] % MOD;

    if (n >= 1)

        sum = (sum + 1ll * p[1] * power[n - 1] % MOD) % MOD;

    for (int i = 2; i <= n; ++ i)

        sum = (sum + 1ll * p[i] * power[n - i] % MOD * (i + 1) % MOD * power[i - 2] % MOD) % MOD;

    printf("%d\n", sum);

    return 0;

}