ソースコード
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
#define ROOP() while(true)
////1
//int main() {
// int f, s;
// cin >> f >> s;
// bool ans = true;
// while (f >= 2 && s >= 1) {
// f -= 2;
// s -= 1;
// ans = !ans;
// }
// if (ans) cout << "K" << endl;
// else cout << "O" << endl;
//
// return 0;
//}
////2
//int main() {
// int N, M;
// cin >> N >> M;
// vector<int> A;
// for (int i = 0; i < N; i++) {
// int tmp;
// cin >> tmp;
// A.push_back(tmp);
// }
// sort(A.begin(), A.end());
// reverse(A.begin(), A.end());
//
// int ans = 0;
// int tmp = 0;
// while (tmp < M) {
// tmp += A[ans];
// ans++;
// }
// cout << ans << endl;
//
// return 0;
//}
////3
//int main() {
// int N, H, W;
// cin >> N >> H >> W;
// vector<string> f;
// for (int i = 0; i < H; i++) {
// string tmp;
// cin >> tmp;
// f.push_back(tmp);
// }
//
// for (int i = 1; i <= N; i++) {
// //横
// int ans1 = 0;
// for (int j = 0; j < H; j++) {
// for (int k = 0; k < W; k++) {
// if (k + i > W) break;
// bool tmp = true;
// for (int l = k; l < k + i; l++) {
// if (f[j][l] == '#') tmp = false;
// }
// if (tmp) {
// ans1++;
// k += i - 1;
// }
// }
// }
//
// //縦
// int ans2 = 0;
// //for (int j = 0; j < W; j++) {
// // for (int k = 0; k < H; k++) {
// // if (k + i > H) break;
// // bool tmp = true;
// // for (int l = k; l < k + i; l++) {
// // if (f[l][j] == '#') tmp = false;
// // }
// // if (tmp) {
// // ans2++;
// // k += i - 1;
// // }
// // }
// //}
//
// cout << max(ans1, ans2) << endl;
// }
//
// return 0;
//}
////4
//int N;
//int t[16];
//int a[16][16];
//
//map<vector<bool>, int> dp;
//int solve(vector<bool> state) {
// if (dp.count(state) == 1) return dp[state];
//
// int ans = INT_MAX;
// for (int i = 0; i < N; i++) {
// if (state[i]) continue;
// int less = 0;
// for (int j = 0; j < N; j++) {
// if (state[j]) less += a[j][i];
// }
// state[i] = true;
// ans = min(ans, t[i] - less + solve(state));
// state[i] = false;
// }
//
// dp[state] = ans;
// return ans;
//}
//
//int main() {
// cin >> N;
// for (int i = 0; i < N; i++) {
// cin >> t[i];
// }
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// cin >> a[i][j];
// }
// }
//
// vector<bool> state;
// vector<bool> state2;
// for (int i = 0; i < N; i++) {
// state.push_back(false);
// state2.push_back(true);
// }
// dp[state2] = 0;
// cout << solve(state) << endl;
//
// return 0;
//}
//5
int N;
vector<int> a;
const int large = 1000000007;
int dp[100000];
int solve(int now) {
if (dp[now] != -1) return dp[now];
int ans = 1;
int old = INT_MAX;
for (int i = now+1; i < N; i++) { //次にどの曲で遊ぶか
if (old == a[i]) continue;
ans += solve(i);
ans %= large;
old = a[i];
}
dp[now] = ans;
return ans;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
a.push_back(tmp);
dp[i] = 1;
}
sort(a.begin(), a.end());
for (int j = N - 1; j >= 0; j--) {
int old = -1;
for (int i = j + 1; i < N; i++) { //次にどの曲で遊ぶか
if (old == a[i]) continue;
dp[j] += dp[i];
dp[j] %= large;
old = a[i];
}
}
cout << dp[0]%large << endl;
return 0;
}
////6
//int main() {
// int N, K;
// cin >> N >> K;
// int num[1005];
// int m = 0;
// for (int i = 0; i < 1005; i++) {
// if (N >= 9) {
// num[i] = 9;
// N -= 9;
// }
// else if (N >= 1) {
// num[i] = N;
// N = 0;
// m = i;
// }
// else {
// num[i] = 0;
// }
// }
//
//
// int c = 1;
// while (c != K) {
// for (int i = 0; i < 1005; i++) {
// if (num[i] >= 1) {
// num[i + 1]++;
// m = max(m,i+1);
// if (num[i + 1] < 10) {
// if (i == 0) {
// num[i]--;
// }
// else {
// num[0] = num[i] - 1;
// num[i] = 0;
// }
// }
// else {
// num[i + 1]--;
// num[i + 1] += num[i];
// if (i == 0) {
// num[i] = 0;
// }
// else {
// num[0] = num[i];
// num[i] = 0;
// }
// }
//
// break;
// }
// }
// bool tmp = true;
// for (int i = 0; i <= m; i++) {
// if (num[i] >= 10) {
// tmp = false;
// break;
// }
// }
// if (tmp) c++;
// }
//
// for (int i = m; i >= 0; i--) {
// cout << num[i];
// }
// cout << endl;
//
// return 0;
//}
////7
//int main() {
//
//
// return 0;
//}
////8
//int main() {
//
//
// return 0;
//}
////9
//int main() {
//
//
// return 0;
//}
////10
//int main() {
//
//
// return 0;
//}