1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9+7;

int lcp[5005][5005], dp[5005][5005];

int main() {
	string s;
	cin >> s;
	int n = s.size();
	for (int i = n - 1; i >= 0; --i) {
		for (int j = n - 1; j >= i; --j) {
			if (s[i] == s[j]) lcp[i][j] = 1 + lcp[i + 1][j + 1];
		}
	}

	dp[0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			dp[i][j] += dp[i][j - 1], dp[i][j] %= MOD;
			int len = min(lcp[i][j], j - i);
			if (i + len >= n || (len < j - i && s[i + len] > s[j + len])) continue;
			dp[j][j + len + 1] += dp[i][j], dp[j][j + len + 1] %= MOD;
		}
	}

	int ans = 0;
	for (int i = 0; i < n; ++i) ans += dp[i][n], ans %= MOD;
	cout << ans << '\n';
}