I am in 90% sleep state...pardon me but the timing of hacker-cup was not suitable for India , it was at night 2:30 am :( .

Why is it so time taking...

<#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<numeric>
#include<vector>

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()
#define sz(a) (a).size()
#define pb push_back

using namespace std;

typedef long long ll;
ll modu = 1000000007;
map <string,ll> mp;
int c=0;
ll f(string s)
{
//cout<<"here:"<<s<<" ";

if(sz(s) == 1) return 0;

if(mp[s]!=0) {return mp[s];}
ll sum = 0;
ll tmp,tmp2;
int arr[2];

arr[0] = 0;
arr[1] = 0;
for(int i = sz(s) ; i >= 2;i--)
{
for(int j = 0; j + i <=sz(s) ; j++)
{
c++;

tmp = 0;
tmp2 = 0;
// int p = 0;
for(int k = j ; k < j + i ; k++)
{
if(s[k] == 'a') { arr[0] = 1;}

if(s[k] == 'b') { arr[1] = 1;}
}
if(arr[0] == 1) {string new_s = s.substr(0,j)+'a'+s.substr(j+i); if(mp[new_s]!=0) tmp = 1 + mp[new_s] ; else tmp = 1 + f(new_s);
}
if(arr[1] == 1){string new_s = s.substr(0,j)+'b'+s.substr(j+i); if(mp[new_s]!=0) tmp = 1 + mp[new_s] ; else tmp2 = 1 + f(s.substr(0,j)+'b'+s.substr(j+i));
}
arr[0] = 0;
arr[1] = 0;

sum =(sum + tmp % modu + tmp2 % modu) % modu;
// mp[s]+=sum;
}
}
mp[s] = sum;
//cout<<mp[s];
return sum;
}


int main()
{
int T;
cin>>T;
string s="aa";
mp[s] = 1;
s="bb";
mp[s] = 1;
s="ab";
mp[s] = 2;
s="ba";
mp[s] = 2;
string S;
while(T--)
{
cin>>S;
c=0;
cout<<(f(S)+1)%1000000007;
cout<<endl;
// cout<<endl<<sz(mp)<<endl;
// cout<<c<<endl;
mp.clear();
}
return 0;
}

why is it exponential  :( :'(  :'(  .

Actually I know why is it exponential, I want to ask, can I change it to polynomial, without changing overall structure of my program.
>