Exploring Pyramids UVA - 1362

#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
const int N=304;
const int mod =1e9;
#define int long long
char a[N];
 int n,f[N][N];
  
 int dp(int l,int r){
 	if(~f[l][r]) return f[l][r];
 	if(l==r) return 1;
 	f[l][r]=0;
 	for(int k=l+1;k<=r;k++){
 		if(a[l]==a[k]) 
 		f[l][r]+=dp(l+1,k-1)*dp(k,r)%mod,f[l][r]%=mod;
 	}
 	return f[l][r];
 }
 signed main(){
 	while(cin>>(a+1))
 	memset(f,-1,sizeof f),cout<<dp(1,strlen(a+1))<<'\n'; 
 }