#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 để đưa xâu con s[l..r] về thành xâu rỗng
int memo[N][N]; 
 
int dp(int l, int r) {
	if (l > r) return 1; 
	if (l == r) return 0; 
	if (l + 1 == r) return (s[l] == s[r]);
	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; // tổng số thao tác cần dùng để xoá đ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 = max(0, (k - l - 1) / 2); // tổng số thao tác cần dùng để xoá đ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]
			int ways = C[cnt][cnt1 + 1]; 
			ans += 1ll * ways * 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+G7kSBjw6FjaCDEkeG7gyDEkcawYSB4w6J1IGNvbiBzW2wuLnJdIHbhu4EgdGjDoG5oIHjDonUgcuG7l25nCmludCBtZW1vW05dW05dOyAKCmludCBkcChpbnQgbCwgaW50IHIpIHsKCWlmIChsID4gcikgcmV0dXJuIDE7IAoJaWYgKGwgPT0gcikgcmV0dXJuIDA7IAoJaWYgKGwgKyAxID09IHIpIHJldHVybiAoc1tsXSA9PSBzW3JdKTsKCWlmICgociAtIGwgKyAxKSAlIDIgPT0gMSkgcmV0dXJuIDA7ICAgCgoJaW50JiBhbnMgPSBtZW1vW2xdW3JdOyAKCWlmIChhbnMgIT0gLTEpIHJldHVybiBhbnM7ICAKCglhbnMgPSAwOwoJaW50IGNudCA9IChyIC0gbCArIDEpIC8gMjsgLy8gdOG7lW5nIHPhu5EgdGhhbyB0w6FjIGPhuqduIGTDuW5nIMSR4buDIHhvw6EgxJFv4bqhbiBbbCwgcl0KCWZvciAoaW50IGsgPSBsICsgMTsgayA8PSByOyBrKyspIHsgLy8gc1trXSBz4bq9IMSR4bupbmcga+G7gSB24bubaSBzW2xdCgkJaWYgKHNbbF0gPT0gc1trXSkgewoJCQlpbnQgY250MSA9IG1heCgwLCAoayAtIGwgLSAxKSAvIDIpOyAvLyB04buVbmcgc+G7kSB0aGFvIHTDoWMgY+G6p24gZMO5bmcgxJHhu4MgeG/DoSDEkW/huqFuIFtsICsgMSwgayAtIDFdCgkJCS8vIENo4buJIGPDsyB0aOG7gyB4b8OhIGPhurdwIChzW2xdLCBzW2tdKSBzYXUga2hpIMSRw6MgeG/DoSDEkW/huqFuIFtsICsgMSwgayAtIDFdCgkJCS8vIENo4buNbiB0aOG7nWkgxJFp4buDbSB4b8OhIMSRb+G6oW4gW2wgKyAxLCBrIC0gMV0gdsOgIGPhurdwIChzW2xdLCBzW2tdKQoJCQkvLyBOaOG7r25nIHRo4budaSDEkWnhu4NtIGPDsm4gbOG6oWkgc+G6vSBsw6AgeG/DoSDEkW/huqFuIFtrICsgMSwgcl0KCQkJaW50IHdheXMgPSBDW2NudF1bY250MSArIDFdOyAKCQkJYW5zICs9IDFsbCAqIHdheXMgKiBkcChsICsgMSwgayAtIDEpICUgTU9EICogZHAoayArIDEsIHIpICUgTU9EOyAKCQkJYW5zICU9IE1PRDsgCgkJfQoJfQoKCXJldHVybiBhbnM7ICAKfQoKaW50IG1haW4oKSB7Cglpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IAoJY2luLnRpZShudWxscHRyKTsgCQoJY2luID4+IHM7IAoJbiA9IHMuc2l6ZSgpOyAgCglzID0gJyAnICsgczsgCgoJcHJlY29tcHV0ZSgpOyAgCgoJbWVtc2V0KG1lbW8sIC0xLCBzaXplb2YgbWVtbyk7IAoJY291dCA8PCBkcCgxLCBuKSA8PCAnXG4nOyAKfQ==

YWFiY2Ni

aabccb