Language: C++

#include<iostream>
#include<vector>
#include<stdint>
using namespace std;
class Factorial;

class ModInt;

class Factorial{
	private:
		int64_t mod;
		int64_t n;
		vector<int64_t> fac, in, fin, prime;
		void calc();
		int64_t rem(int64_t a) {
			if (mod == 0) return a;
			return (a % mod + mod) % mod;
		}
	public:
		Factorial(int64_t mod, int64_t n);
		int64_t add(int64_t a, int64_t b);
		int64_t sub(int64_t a, int64_t b);
		int64_t mul(int64_t a, int64_t b);
		int64_t div(int64_t a, int64_t b);
		int64_t rem(int64_t a, int64_t b);
		int64_t ior(int64_t a, int64_t b);
		int64_t iand(int64_t a, int64_t b);
		int64_t ixor(int64_t a, int64_t b);
		int64_t lshift(int64_t a, int64_t b);
		int64_t rshift(int64_t a, int64_t b);
		int64_t pow(int64_t a, int64_t b);
		int64_t hom(int64_t a, int64_t b);
		int64_t comb(int64_t a, int64_t b);
		int64_t perm(int64_t a, int64_t b);
		int64_t gcd(int64_t a, int64_t b);
		int64_t fact(int64_t a);
		int64_t fInv(int64_t a);
		int64_t inv(int64_t a);
		int64_t getMod() {return mod;}
		vector<pair<int64_t, int> > getPrime(int64_t a);
		ModInt create(int64_t n);
		ModInt create();
};

/**
 * 剰余を計算するための専用のIntクラスです。
 * 
 */
class ModInt {
	private:
		Factorial *f;
		int64_t n;
	public:
		friend class Factorial;
		friend istream& operator>>(istream &s, ModInt &i);
		friend ostream& operator<<(ostream &s, const ModInt &i);
		ModInt (Factorial *f) {ModInt::f = f, n = 0;}
		ModInt (Factorial *f, int64_t n) {ModInt::f = f, ModInt::n = n;}
		ModInt () {}
		void set(Factorial *f) {ModInt::f = f, n = 0;}
		void set(Factorial *f, int64_t n) {ModInt::f = f, ModInt::n = n;}
		inline operator int64_t() const{return n;}
		inline ModInt& operator++() {n = (*f).add(n, 1); return *this;}
		const ModInt operator++(int) {const ModInt ret = *this; ++(*this); return ret;}
		inline ModInt& operator--() {n = (*f).sub(n, 1); return *this;}
		const ModInt operator--(int) {const ModInt ret = *this; --(*this); return ret;}
		inline const ModInt operator+() const{ return *this;}
		const ModInt operator-() const{ return (*f).create(-n);}
		inline ModInt& operator=(const int64_t& x) {n = (*f).rem(x, (*f).getMod()); return *this;}
		inline ModInt& operator+=(const int64_t& x) {n = (*f).add(n, x); return *this;}
		inline ModInt& operator+(const ModInt& x) { return ModInt(*this) += x;}
		inline ModInt& operator-=(const int64_t& x) {n = (*f).sub(n, x); return *this;}
		inline ModInt& operator-(const ModInt& x) { return ModInt(*this) -= x;}
		inline ModInt& operator*=(const int64_t& x) {n = (*f).mul(n, x); return *this;}
		inline ModInt& operator*(const ModInt& x) { return ModInt(*this) *= x;}
		inline ModInt& operator/=(const int64_t& x) {n = (*f).div(n, x); return *this;}
		inline ModInt& operator/(const ModInt& x) { return ModInt(*this) /= x;}
		inline ModInt& operator%=(const int64_t& x) {n = (*f).rem(n, x); return *this;}
		inline ModInt& operator%(const ModInt& x) { return ModInt(*this) %= x;}
		inline ModInt& operator|=(const int64_t& x) {n = (*f).ior(n, x); return *this;}
		inline ModInt& operator|(const ModInt& x) { return ModInt(*this) |= x;}
		inline ModInt& operator&=(const int64_t& x) {n = (*f).iand(n, x); return *this;}
		inline ModInt& operator&(const ModInt& x) { return ModInt(*this) &= x;}
		inline ModInt& operator^=(const int64_t& x) {n = (*f).ixor(n, x); return *this;}
		inline ModInt& operator^(const ModInt& x) { return ModInt(*this) ^= x;}
		inline ModInt& operator<<=(const int64_t& x) {n = (*f).lshift(n, x); return *this;}
		inline ModInt& operator<<(const ModInt& x) { return ModInt(*this) <<= x;}
		inline ModInt& operator>>=(const int64_t& x) {n = (*f).rshift(n, x); return *this;}
		inline ModInt& operator>>(const ModInt& x) { return ModInt(*this) >>= x;}
		ModInt pow(ModInt x) { return *(new ModInt(f, (*f).pow(n, x)));}
		ModInt pow(int64_t x) { return *(new ModInt(f, (*f).pow(n, x)));}
		ModInt H(ModInt x) {return *(new ModInt(f, (*f).hom(n, x)));}
		ModInt H(int64_t x) {return *(new ModInt(f, (*f).hom(n, x)));}
		ModInt C(ModInt x) {return *(new ModInt(f, (*f).comb(n, x)));}
		ModInt C(int64_t x) {return *(new ModInt(f, (*f).comb(n, x)));}
		ModInt P(ModInt x) {return *(new ModInt(f, (*f).perm(n, x)));}
		ModInt P(int64_t x) {return *(new ModInt(f, (*f).perm(n, x)));}
		ModInt fact() {return *(new ModInt(f, (*f).fact(n)));}
};

istream& operator>>(istream &s, ModInt &i) {
	s >> i.n;
	return s;
}

ostream& operator<<(ostream &s, const ModInt& i) {
	s << i.n;
	return s;
}

ModInt Factorial::create(int64_t n) {
	return *(new ModInt(this, rem(n)));
}

ModInt Factorial::create() {
	return create(0);
}

/**
 * 関数の初期化を行います。この時に空間O(n)と計算時間O(n)が必要なことに注意してください。
 * @param mod 用いる余り ※必ず素数にすること
 * @param n 用意する階乗の範囲
 */
Factorial::Factorial(int64_t mod, int64_t n) {
	if (mod == 0) n = 0;
	if (n <= 0) n = 1;
	Factorial::mod = mod;
	Factorial::n = n;
	fac.resize(n + 1, 1);
	in.resize(n + 1, 1);
	fin.resize(n + 1, 1);
	prime.resize(n + 1, 1);
	calc();
}

void Factorial::calc() {
	for (int64_t i = 2;i <= n;++ i) {
		fac[i] = mul(fac[i - 1], i);
		in[i] = mod - mul(in[mod % i], mod / i);
		fin[i] = mul(fin[i - 1], in[i]);
		if (prime[i] < 2) for (int64_t j = i, l = n - i;j < l;j += i) if (prime[j] < 2) prime[j] = i;
	}
}

/**
 * a+bをmod環境下で返します。
 * @param a 足す値
 * @param b 足される値
 * @return (a + b) % mod
 */
int64_t Factorial::add(int64_t a, int64_t b) {
	return rem(a + b);
}

/**
 * a-bをmod環境下で返します。
 * @param a 引く値
 * @param b 引かれる値
 * @return (a - b) % mod
 */
int64_t Factorial::sub(int64_t a, int64_t b) {
	return rem(a - b);
}

/**
 * a*bをmod環境下で返します。
 * @param a 掛ける値
 * @param b 掛けられる値
 * @return (a * b) % mod
 */
int64_t Factorial::mul(int64_t a, int64_t b) {
	return rem(a * b);
}

/**
 * a/bをmod環境下で返します。O(log(mod))な点にご注意ください
 * @param a 割る値
 * @param b 割られる値
 * @return (a / b) % mod
 */
int64_t Factorial::div(int64_t a, int64_t b) {
	if (b <= n) return mul(a, in[b]);
	return mul(a, pow(b, mod - 2));
}

/**
 * a|bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a | b
 */
int64_t Factorial::ior(int64_t a, int64_t b) {
	return rem(a | b);
}

/**
 * a&bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a & b
 */
int64_t Factorial::iand(int64_t a, int64_t b) {
	return a & b;
}

/**
 * a^bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a ^ b
 */
int64_t Factorial::ixor(int64_t a, int64_t b) {
	return rem(a ^ b);
}

/**
 * a<<bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a << b
 */
int64_t Factorial::lshift(int64_t a, int64_t b) {
	return mul(a, pow(2, b));
}
/**
 * a>>bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a >> b
 */
int64_t Factorial::rshift(int64_t a, int64_t b) {
	return div(a, pow(2, b));
}

/**
 * a%bを返します。
 * @param a 割る値
 * @param b 割られる値
 * @return a % b
 */
int64_t Factorial::rem(int64_t a, int64_t b) {
	return a % b;
}

/**
 * aのb乗をmod環境下で返します。
 * @param a 底
 * @param b 冪指数
 * @return pow(a, b) % mod
 */
int64_t Factorial::pow(int64_t a, int64_t b) {
	if (b < 0) return pow(a, b + mod - 1);
	switch(b) {
		case 0: return 1;
		case 1: return a;
		case 2: return mul(a, a);
	}
	return mul(pow(pow(a, b >> 1), 2), pow(a, b & 1));
}

/**
 * aHb(重複組み合わせ)をmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aHb) % mod
 */
int64_t Factorial::hom(int64_t a, int64_t b) {
	return comb(a + b - 1, b);
}

/**
 * aCb(組み合わせ)をmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aCb) % mod
 */
int64_t Factorial::comb(int64_t a, int64_t b) {
	return mul(perm(a, b), fInv(b));
}

/**
 * aPb(順列)をmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aPb) % mod
 */
int64_t Factorial::perm(int64_t a, int64_t b) {
	return mul(fact(a), fInv(a - b));
}

/**
 * gcd(a, b)を返します。
 * @param a 互除法をしたい値
 * @param b 互除法をしたい値
 * @return gcd(a, b)
 */
int64_t Factorial::gcd(int64_t a, int64_t b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

/**
 * a!をmod環境下で返します。
 * @param a 計算する値
 * @return a! % mod
 */
int64_t Factorial::fact(int64_t a) {
	if (a <= n) return fac[a];
	int64_t ret = fac[n];
	for (int64_t i = n;i < a;++ i) ret = mul(ret, i + 1);
	return ret;
}

/**
 * a!の-1乗をmod環境下で返します。
 * @param a 計算する値
 * @return pow(a!, -1) % mod
 */
int64_t Factorial::fInv(int64_t a) {
	if (a <= n) return fin[a];
	return pow(fact(a), mod - 2);
}

/**
 * aの-1乗をmod環境下で返します。
 * @param a 計算する値
 * @return pow(a, -1) % mod
 */
int64_t Factorial::inv(int64_t a) {
	if (a <= n) return in[a];
	return pow(a, -1);
}

/**
 * aの素因数を返します。
 * @param a 素因数を求める値
 * @return 素因数
 */
vector<pair<int64_t, int> > Factorial::getPrime(int64_t a) {
	vector<pair<int64_t, int> > ret;
	if (a <= n) {
		while (a > 1) {
			ret.push_back(make_pair(prime[a], 1));
			a /= prime[a];
			while (prime[a] == ret[ret.size() - 1].first) {
				++ ret[ret.size() - 1].second;
				a /= prime[a];
			}
		}
		return ret;
	}
	for (int i = 2;i * i <= a;++ i) {
		if (a % i == 0) {
			ret.push_back(make_pair(i, 1));
			a /= i;
			while (a % i == 0) {
				++ ret[ret.size() - 1].second;
				a /= i;
			}
		}
	}
	if (a > 1) ret.push_back(make_pair(a, 1));
	return ret;
}

const int MAX = 100001;
const int MOD = 1000000007; // 今回使う余り
int main() {
	Factorial f(MOD, MAX);
	static int N;
	ModInt A(&f), ans(&f, 0);
	cin >> N;
	static ModInt sum[MAX];
	sum[0].set(&f, f.fact(N));
	for (int i = 1;i <= N;++ i) {
		sum[i].set(&f, sum[i - 1] + f.fact(N) / f.create(i + 1));
	}
	for (int i = 0;i < N;++ i) {
		cin >> A;
		ans += A * (sum[i] + sum[N - i - 1] - sum[0]);
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

全通り試すので一種の対称性が成り立つ
まず、1番目の値について考えると、全N!回の中で1番目と連結なパターンはN!通り
2番目と連結なパターンは(N!)/2通り
3番目と連結なパターンは(N!)/3通り
……
j番目と連結なパターンは(N!)/j通り
ということは、例えば入力例2で見てみると、1番目の値が計算に使われる回数はN!+(N!)/2+(N!)/3+(N!)/4=24+12+8+6=50
2番目の値が計算に使われる回数は(N!)/2+N!+(N!)/2+(N!)/3=12+24+12+8=56
3番目と4番目は対称なので、合計は1*50+1*56+1*56+1*50=212回
後はN!+(N!)/2+……が分かっていれば良いので、累積和しておけばO(1)で求められるから結局O(N)で解ける
*/

Compiler output:
a.cc:3:9: fatal error: stdint: No such file or directory
    3 | #include<stdint>
      |         ^~~~~~~~
compilation terminated.