ソースコード
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
using namespace std;
long long N, M, K,a,b,c,d,e,H,W;
long long an[300000];
long long ni[300000]={};
long long A[2000][2000] = {};
long long t[200001] = {};
bool f[601][601];
string S;
set <long long>sll;
vector <long long>vll,vl;
typedef pair<long long, long long> pl;
pl buf;
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> t[i];
vll.push_back(t[i]);
}
sort(vll.begin(), vll.end());
a = 1;
ni[0] = 1;
for (int i = 1; i < N; i++) {
if (vll[i] == vll[i - 1]) {
ni[i] = ni[i - 1];
}
else {
ni[i] = a;
}
a +=ni[i];
a /= 1000000009;
}
c = 0;
for (int i = 0; i <= N; i++) {
c += ni[i];
c /= 1000000009;
}
cout << c << endl;
return 0;
}