#include #include using namespace std; #define MOD(N) ((N) % 1000000009) int N; typedef long long ll; vector a; int main() { cin >> N; for(int i = 0;i < N;i++) { ll t; cin >> t; a.push_back(t); } int sz = N; while(sz - 4 >= 1) { for(int i = 0;i + 4 < sz;i++) { a[i] = MOD(a[i] + 4 * a[i + 1] + 6 * a[i + 2] + 4 * a[i + 3] + a[i + 4]); } sz -= 4; } while(sz > 1) { for(int i = 0;i < sz - 1;i++) { a[i] = MOD(a[i] + a[i + 1]); } sz--; } cout << a[0] << endl; return 0; }