#include <bits/stdc++.h> 
 
using namespace std;  
 
typedef long long ll;  
typedef pair<int, int> ii;  
 
const int INF = 1e9;  
const ll LINF = 1e18;  
 
const int MOD = 1e9 + 7;  
const int N = 5e2 + 5; 
 
int n;  
string s;   
 
int C[N][N]; // C[n][k] = Tổ hợp chập k của n 
 
void precompute() {
	for (int i = 0; i <= n; i++) {
		C[i][0] = 1; 
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD; 
		}
	}
}
 
// dp(l, r) = Số cách để xoá hết đoạn [l, r] của xâu s 
int memo[N][N]; 
 
int dp(int l, int r) {
	if (l > r) return 1; 
	if ((r - l + 1) % 2 == 1) return 0;   
 
	int& ans = memo[l][r]; 
	if (ans != -1) return ans;  
 
	ans = 0;
	int cnt = (r - l + 1) / 2; // Số bước cần dùng để xoá hết đoạn [l, r]
	for (int k = l + 1; k <= r; k++) { // s[k] sẽ đứng kề với s[l]
		if (s[l] == s[k]) {
			int cnt1 = (k - l - 1) / 2; // Số bước cần dùng để xoá hết đoạn [l + 1, k - 1]
			// Chỉ có thể xoá cặp (s[l], s[k]) sau khi đã xoá đoạn [l + 1, k - 1]
			// Chọn thời điểm xoá đoạn [l + 1, k - 1] và cặp (s[l], s[k])
			// Những thời điểm còn lại sẽ là xoá đoạn [k + 1, r]
			ans += 1ll * C[cnt][cnt1 + 1] * dp(l + 1, k - 1) % MOD * dp(k + 1, r) % MOD; 
			ans %= MOD; 
		}
	}
 
	return ans;  
}
 
int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> s; 
	n = s.size();  
	s = ' ' + s; 
 
	precompute();  
 
	memset(memo, -1, sizeof memo); 	
 
	cout << dp(1, n) << '\n'; 
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+IAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsgIAoKdHlwZWRlZiBsb25nIGxvbmcgbGw7ICAKdHlwZWRlZiBwYWlyPGludCwgaW50PiBpaTsgIAoKY29uc3QgaW50IElORiA9IDFlOTsgIApjb25zdCBsbCBMSU5GID0gMWUxODsgIAoKY29uc3QgaW50IE1PRCA9IDFlOSArIDc7ICAKY29uc3QgaW50IE4gPSA1ZTIgKyA1OyAKCmludCBuOyAgCnN0cmluZyBzOyAgIAoKaW50IENbTl1bTl07IC8vIENbbl1ba10gPSBU4buVIGjhu6NwIGNo4bqtcCBrIGPhu6dhIG4gCgp2b2lkIHByZWNvbXB1dGUoKSB7Cglmb3IgKGludCBpID0gMDsgaSA8PSBuOyBpKyspIHsKCQlDW2ldWzBdID0gMTsgCgkJZm9yIChpbnQgaiA9IDE7IGogPD0gaTsgaisrKSB7CgkJCUNbaV1bal0gPSAoQ1tpIC0gMV1bal0gKyBDW2kgLSAxXVtqIC0gMV0pICUgTU9EOyAKCQl9Cgl9Cn0KCi8vIGRwKGwsIHIpID0gU+G7kSBjw6FjaCDEkeG7gyB4b8OhIGjhur90IMSRb+G6oW4gW2wsIHJdIGPhu6dhIHjDonUgcyAKaW50IG1lbW9bTl1bTl07IAoKaW50IGRwKGludCBsLCBpbnQgcikgewoJaWYgKGwgPiByKSByZXR1cm4gMTsgCglpZiAoKHIgLSBsICsgMSkgJSAyID09IDEpIHJldHVybiAwOyAgIAoKCWludCYgYW5zID0gbWVtb1tsXVtyXTsgCglpZiAoYW5zICE9IC0xKSByZXR1cm4gYW5zOyAgCgoJYW5zID0gMDsKCWludCBjbnQgPSAociAtIGwgKyAxKSAvIDI7IC8vIFPhu5EgYsaw4bubYyBj4bqnbiBkw7luZyDEkeG7gyB4b8OhIGjhur90IMSRb+G6oW4gW2wsIHJdCglmb3IgKGludCBrID0gbCArIDE7IGsgPD0gcjsgaysrKSB7IC8vIHNba10gc+G6vSDEkeG7qW5nIGvhu4EgduG7m2kgc1tsXQoJCWlmIChzW2xdID09IHNba10pIHsKCQkJaW50IGNudDEgPSAoayAtIGwgLSAxKSAvIDI7IC8vIFPhu5EgYsaw4bubYyBj4bqnbiBkw7luZyDEkeG7gyB4b8OhIGjhur90IMSRb+G6oW4gW2wgKyAxLCBrIC0gMV0KCQkJLy8gQ2jhu4kgY8OzIHRo4buDIHhvw6EgY+G6t3AgKHNbbF0sIHNba10pIHNhdSBraGkgxJHDoyB4b8OhIMSRb+G6oW4gW2wgKyAxLCBrIC0gMV0KCQkJLy8gQ2jhu41uIHRo4budaSDEkWnhu4NtIHhvw6EgxJFv4bqhbiBbbCArIDEsIGsgLSAxXSB2w6AgY+G6t3AgKHNbbF0sIHNba10pCgkJCS8vIE5o4buvbmcgdGjhu51pIMSRaeG7g20gY8OybiBs4bqhaSBz4bq9IGzDoCB4b8OhIMSRb+G6oW4gW2sgKyAxLCByXQoJCQlhbnMgKz0gMWxsICogQ1tjbnRdW2NudDEgKyAxXSAqIGRwKGwgKyAxLCBrIC0gMSkgJSBNT0QgKiBkcChrICsgMSwgcikgJSBNT0Q7IAoJCQlhbnMgJT0gTU9EOyAKCQl9Cgl9CgoJcmV0dXJuIGFuczsgIAp9CgppbnQgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgCgljaW4udGllKG51bGxwdHIpOyAJCgljaW4gPj4gczsgCgluID0gcy5zaXplKCk7ICAKCXMgPSAnICcgKyBzOyAKCglwcmVjb21wdXRlKCk7ICAKCgltZW1zZXQobWVtbywgLTEsIHNpemVvZiBtZW1vKTsgCQoJCgljb3V0IDw8IGRwKDEsIG4pIDw8ICdcbic7IAp9

YWFiY2Ni

aabccb