1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
 *  Copyright (C) 2019  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

int LIMIT = 1000000000;
unordered_map<int, unsigned int> cache;

int factorial(int x) {
	int n = x;
	unsigned int f = 1;
	while (x > 1) {
		if (cache.count(x)) {
			cache[n] = (f * cache[x]) % LIMIT;
			return cache[n];
		}
		f = (f * x--) % LIMIT;
	}
	cache[n] = f % LIMIT;
	return cache[n];
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, k;
	string s;

	vector<int> radius;
	vector<string> center;

	cin >> n;
	vector<int> previous(n + 1);
	vector<int> row(n + 1);

	for (int i = 0; i < n; ++i) {
		cin >> k >> s;
		radius.emplace_back(k);
		center.emplace_back(s);
	}

	if (center[0] == center[1] && center[1] == center[2]) {
		auto r = max_element(begin(radius), end(radius));

		// init the dynamic programming row
		for (int i = 0; i <= n; ++i) {
			previous[i] = i + 1;
		}
		// compute
		for (int k = 1; k <= *r; ++k) {
			row[0] = previous[1];
			for (int i = 1; i <= n; ++i) {
				row[i] = (row[i - 1] + previous[i]) % LIMIT;
			}
			swap(row, previous);
		}

		cout << row[*r + 1] + 7 << endl;
	} else {
		cout << "dunno" << endl;
	}

	return 0;
}