816D - Karen and Test - CodeForces Solution

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#include <bits/stdc++.h>
#ifdef LOCAL
#define VDBG(X...) (cerr<<__func__<<':'<<__LINE__<<':'<<#X<<": ",DBG(X))
#define DBG(X...) eprn(X)
#else
#define VDBG(...)
#define DBG(...)
#define endl '\n' // remove this line for interactive tasks
#ifdef assert
#undef assert
#endif
#define assert(expr) (expr) || (__builtin_unreachable(), 0)
#endif
#define FORT(T, I, S, N) for(T I = (S); I < (N); ++I)
#define RFORT(T, I, S, N) for(T I = (S); I > (N); --I)
#define FOR(I, S, N) FORT(ptrdiff_t, I, (S), (N)) // ptrdiff_t = basically same as isize in rust
#define RFOR(I, S, N) RFORT(ptrdiff_t, I, (S), (N))
#define FORI(N) FOR(i, 0, (N))
#define FORJ(N) FOR(j, 0, (N))
#define FORK(N) FOR(k, 0, (N))
#define RFORI(N) RFOR(i, (N)-1, -1)
#define RFORJ(N) RFOR(j, (N)-1, -1)
#define SPOON(N) RFOR(k, (N)-1, -1)
#define ALL(X) (X).begin(), (X).end()
#define RALL(X) (X).rbegin(), (X).rend()
#define RD(T, X...) T X; rd(X);
#define YN(B) ((B)?"YES":"NO")
#define  A auto
#define _T template
#define _Y typename
#define _SP(A,B,C) bool f=!0;for(A){if(f){f=!1;}else{B;}C;}
#define _I1(C) _T<_Y T>ostream&operator<<(ostream&o,C<T>const&v){_SP(const A&x:v,o<<' ',o<<x)return o;}_T<_Y T>istream&operator>>(istream&i,C<T>&v){for(A&x:v){i>>x;}return i;}
#define _I2(C) _T<_Y T,_Y Y>ostream&operator<<(ostream&o,C<T,Y>const&v){_SP(const auto&x:v,o<<endl,o<<x)return o;}
using namespace std;constexpr long double PI=3.1415926535897932384626433832795029L;_T<_Y T>using V=vector<T>;_T<_Y T,_Y Y>using P=pair<T,Y>;_T<_Y K>using uset=unordered_set<K>;_T<_Y K>using umultiset=unordered_multiset<K>;_T<_Y K,_Y V>using umap=unordered_map<K,V>;_T<_Y K,_Y V>using umultimap=unordered_multimap<K,V>;using i64=int64_t;using u64=uint64_t;using ll=i64;using i32=int32_t;using u32=uint32_t;using I=i32;using i16=int16_t;using u16=uint16_t;using i8=int8_t;using u8=uint8_t;_I1(V);_I1(set);_I1(multiset);_I1(unordered_set);_I1(unordered_multiset);_I1(deque);_I1(queue);_I2(map);_I2(multimap);_I2(unordered_map);_I2(unordered_multimap);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());_T<_Y T,_Y Y>bool umin(T&a,const Y&b){return b<a&&(a=b,!0);}_T<_Y T,_Y Y>bool umax(T&a,const Y&b){return b>a&&(a=b,!0);}_T<_Y T,_Y Y>ostream&operator<<(ostream&o,pair<T,Y>const&p){return o<<p.first<<' '<<p.second;}_T<_Y T,_Y Y>istream&operator>>(istream&i,pair<T,Y>&p){return i>>p.first>>p.second;}_T<_Y T,size_t N>ostream&operator<<(ostream&o,array<T,N>const&v){_SP(const A&x:v,o<<' ',o<<x)return o;}_T<_Y T,size_t N>istream&operator>>(istream&i,array<T,N>&v){for(A&x:v){i>>x;}return i;}_T<size_t S=0,_Y...T>struct _Tio{static inline void i(istream&i,tuple<T...>&t){if constexpr(S<sizeof...(T)){i>>get<S>(t);_Tio<S+1,T...>::i(i,t);}}static inline void o(ostream&o,tuple<T...>const&t){if constexpr(S<sizeof...(T)){if(S)o<<' ';o<<get<S>(t);_Tio<S+1,T...>::o(o,t);}}};_T<_Y...T>istream&operator>>(istream&i,tuple<T...>&t){return _Tio<0,T...>::i(i,t),i;}_T<_Y...T>ostream&operator<<(ostream&o,tuple<T...>&t){return _Tio<0,T...>::o(o,t),o;}_T<_Y...S>inline void rd(S&...a){A t=forward_as_tuple(a...);cin>>t;}_T<_Y T>inline T read(){T x;cin>>x;return x;}_T<_Y T>inline V<T>read(size_t n){V<T>v(n);for(T&x:v)cin>>x;return v;}_T<_Y...S>inline void pr(const S&...a){(cout<<...<<a);}_T<_Y ...S>inline void prn(const S&...a){(cout<<...<<a)<<endl;}_T<_Y...S>inline void spr(const S&...a){A t=forward_as_tuple(a...);cout<<t;}_T<_Y...S>inline void sprn(const S&...a){spr(a...);cout<<endl;}_T<_Y...S>inline void epr(const S&...a){A t=forward_as_tuple(a...);cerr<<t<<' ';}_T<_Y...S>inline void eprn(const S&...a){epr(a...);cerr<<endl;}

// https://youtu.be/pfkBYHFZAt8
template<typename T, unsigned long long MOD> struct Mint {
  T n;
  constexpr void chk() {n>=0?n%=MOD:(n=-n%MOD)?n=MOD-n:0;}
  constexpr Mint():n(0){} constexpr Mint(const Mint &m):n(m.n){chk();}
#define _CTOR(T) constexpr Mint(unsigned T n):n(n%MOD){} constexpr Mint(T n):n(n){chk();}
  _CTOR(long long); _CTOR(long); _CTOR(int); _CTOR(short); _CTOR(char);
#undef _CTOR
  constexpr Mint operator+() const { return *this; }
  constexpr Mint operator-() const { return Mint(MOD - n); }
#define _OP(OPP,OOP,OOPP,CODE) \
  template<typename Y> constexpr Mint &OOPP(const Mint<Y, MOD> &rhs) { return CODE; } \
  template<typename J> constexpr Mint &OOPP(const J &rhs) { return*this OPP Mint(rhs); } \
  template<typename J> constexpr friend Mint OOP(const Mint &lhs, const J &rhs) { return +lhs OPP rhs; }
  _OP(+=,operator+,operator+=,(n+=rhs.n,chk(),*this));
  _OP(-=,operator-,operator-=,(n-=rhs.n,chk(),*this));
  _OP(*=,operator*,operator*=,(n*=rhs.n,chk(),*this));
  _OP(/=,operator/,operator/=,(*this*=rhs.inv()));
#undef _OP
  constexpr Mint &operator++() { return *this += 1; } constexpr Mint operator++(int) { Mint ret(n); ++*this; return ret; }
  constexpr Mint &operator--() { return *this -= 1; } constexpr Mint operator--(int) { Mint ret(n); --*this; return ret; }
  template<typename J> constexpr friend bool operator==(const Mint &lhs, const Mint<J,MOD> &rhs) { return lhs.n==rhs.n; }
  template<typename J> constexpr friend bool operator!=(const Mint &lhs, const Mint<J,MOD> &rhs) { return lhs.n!=rhs.n; }
  template<typename J> constexpr friend bool operator==(const Mint &lhs, const J &rhs) { return lhs==Mint(rhs); }
  template<typename J> constexpr friend bool operator!=(const Mint &lhs, const J &rhs) { return lhs!=Mint(rhs); }
  friend constexpr ostream &operator<<(ostream &o, const Mint<T, MOD> &m) { return o << m.n; }
  friend constexpr istream &operator>>(istream &i, Mint<T, MOD>&m){ i>>m.n; m.chk(); return i; }
  constexpr Mint pow(unsigned long long m) const { Mint a(n), ret(1); for(;m;a*=a,m/=2)if(m%2)ret*=a; return ret; }
  // only works if MOD is a prime number (in that case a^(MOD-1) = 1, a^(MOD-2) = a^-1)
  // otherwise replace MOD-2 with φ(MOD)-1 (Euler's function)
  constexpr Mint inv() const {return pow(MOD-2);}
};

static_assert(Mint<long long, 998244353>(5) / 2 == 499122179);
static_assert(Mint<long long, 998244353>(5) - 5 == 0);
static_assert(Mint<long long, 998244353>(5) - 6 == 998244352);

using Mi = Mint<ll, 1000000007>;

void stupid0(V<ll> &v, bool a) {
  A n = v.size();
  V<ll> nv(n-1);
  FORI(n-1) {
    if (i%2 == a) nv[i] = v[i] - v[i+1];
    else nv[i] = v[i] + v[i+1];
  }
  v = nv;
}

ll stupid1(V<ll> v) {
  bool x = true;
  while (v.size() > 1) {
    stupid0(v, x);
    if (v.size() % 2 == 1) x= !x;
  }
  return v[0];
}

V<ll> STUPID(I n) {
  V<ll> ans(n);
  V<ll> v(n);
  FORI(n) {
    v[i] = 1;
    ans[i] = stupid1(v);
    v[i] = 0;
  }
  return ans;
}
/*
1: 1
2: 1  1
3: 1  2 -1
4: 1 -1  1 -1

5: 1  0  2  0  1
6: 1  1  2  2  1   1
7: 1  2  1  4 -1   2 -1
8: 1 -1  3 -3  3  -3  1  -1

9: 1  0  4  0  6   0  4   0   1
10:1  1  4  4  6   6  4   4   1    1
11:1  2  3  8  2  12 -2   8  -3    2  -1
12:1 -1  5 -5 10 -10 10 -10   5   -5   1   -1

13:1  0  6  0 15   0 20   0  15    0   6    0   1
14:1  1  6  6 15  15 20  20  15   15   6    6   1   1
15:1  2  5 12  9  30  5  40  -5   30  -9   12  -5   2  -1
16:1 -1  7 -7 21 -21 35 -35  35  -35  21  -21   7  -7   1  -1

17:1  0  8  0 28   0 56   0  70    0  56    0  28   0   8   0  1
18:1  1  8  8 28  28 56  56  70   70  56   56  28  28   8   8  1  1
19:1  2  7 16 20  56 28 112  14  140 -14  112 -28  56 -20  16 -7  2 -1
20:1 -1  9 -9 36 -36 84 -84 126 -126 126 -126  84 -84  36 -36  9 -9  1 -1
 */
V<Mi> fac;
Mi fact(ll n) {
  //return fac[n];
  Mi ans = 1;
  FORI(n) ans *= i+1;
  return ans;
}
V<Mi> pasc;
Mi pascal(ll n, ll k) {
  return pasc[k];
  //return fact(n) / (fact(k) * fact(n - k));
}
ll smart_pascal_n(I n) {
  if (n % 4 <= 2 && n % 4 >= 1) return (n-1)/2;
  if (n % 4 == 3) return (n - 3) / 2;
  return n / 2 - 2;
}
V<Mi> smart(I n) {
  V<Mi> ans(n);
  if (n % 4 <= 2 && n % 4 >= 1) {
    for(I i = 0; i < n; i += (3-n%4)) ans[i] = pascal((n-1)/2, i/2);
  } else if (n % 4 == 3) {
    FORI(n-1) ans[i] = pascal((n-3)/2, i/2);
    RFOR(i, n-1, 0) {
      if (i % 2) ans[i] += ans[i-1];
      else ans[i] -= ans[i-1];
    }
  } else {
    FORI(n-2) ans[i] = pascal(n/2-2, i/2);
    RFORI(n) {
      if (i >= 2) ans[i] += ans[i - 2];
      if (i % 2) ans[i] = -ans[i];
    }
  }
  return ans;
}
void test() {
  //prn(STUPID(20));
  FORI(64) {
    if ((i+1) % 4 != 0) continue;
    A stup = STUPID(i+1);
    V<Mi> stup2(i+1);
    FORJ(i+1) stup2[j] = stup[j];
    A sm = smart(i + 1);
    if (stup2 == sm) continue;
    pr(i+1,':');
    prn("stupid");
    for(I j = 0; j < stup.size(); j += 1) {
      cout << stup[j] << ' ';
    }
    prn();
    prn("smart");
    for(I j = 0; j < sm.size(); j += 1) {
      if (sm[j].n > (1000000007/2)) pr(sm[j].n - 1000000007, ' ');
      else cout << sm[j] << ' ';
    }
    prn();
    prn();
  }
}

void solve() {
  //prn(stupid1({1,2,3}));
  RD(I, n);
  A v = read<Mi>(n);
  ll pn = smart_pascal_n(n);
  fac.resize(pn+1);
  pasc.resize(pn+1);
  fac[0] = 1;
  FORI(pn) fac[i+1] = fac[i] * (i+1);
  FORI(pn+1) pasc[i] = fac[pn] / (fac[i] * fac[pn - i]);
  Mi ans;
  A cont = smart(n);
  FORI(n) ans += cont[i] * v[i];
  prn(ans);
}

int main() {ios_base::sync_with_stdio(!1);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(15);srand(chrono::steady_clock::now().time_since_epoch().count());
  solve();
}