#include using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define rrep(i,n) for (int i = (int)(n)-1; i>=0; --i) #define For(i,a,b) for(auto i=(a);i<=(b);++i) #define rFor(i,a,b) for(auto i=(b);i>=(a);--i) #define call(var) cerr<<#var<<"="<; using vl = vector; using vb = vector; using Graph = vector; using P = pair; const int MOD=(int)1e9+7; const int INF=(int)1e9; const ll LINF=(ll)1e18; const double pi = acos(-1); template inline bool chmax(t&a,u b){if(a inline bool chmin(t&a,u b){if(b istream& operator>>(istream& is, vector& a){rep(i,a.size()) is >> a[i]; return is;} template ostream& operator<<(ostream& os, vector& a){rep(i,a.size()) os << a[i] << " "; return os;} template istream& operator>>(istream& is, pair& p){is >> p.first >> p.second; return is;} template ostream& operator<<(ostream& os, const pair& p){os << "("<< p.first << "," << p.second << ")"; return os;} template ostream& operator<<(ostream& os, const map& mp){for(auto& t : mp) os << t.first << " " << t.second << "\n"; return os;} struct mint { long long x; mint(long long x=0):x((x%MOD+MOD)%MOD){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= MOD) x -= MOD; return *this; } mint& operator-=(const mint a) { if ((x += MOD-a.x) >= MOD) x -= MOD; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this; } mint operator+(const mint a) const { mint res(*this); return res+=a; } mint operator-(const mint a) const { mint res(*this); return res-=a; } mint operator*(const mint a) const { mint res(*this); return res*=a; } mint pow(long long t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime MOD mint inv() const { return pow(MOD-2); } mint& operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& oj); }; istream& operator>>(istream& is, mint& a){return is >> a.x;} ostream& operator<<(ostream& os, const mint& a){return os << a.x;} mint factorial(int n){ mint res = 1; for(int i=1;i<=n;++i){ res *= i; } return res; } mint nCr(int n,int r){ mint numerator = 1; if(r > n - r) r = n - r; for(int i=n;i>n-r;--i){ numerator *= i; } mint denominator = 1; for(int i=1;i<=r;++i){ denominator *= i; } return numerator/denominator; } int main(){ int n;cin >> n; vector a(n); cin >> a; for(int i=0;i