/*

卡特兰数取模 由于数据范围小，直接做。

考试时断网。忘记卡特兰数公式，推错了只有5分。

数学公式要记别每次都现用现搜！！！

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int f[];

int n,m,ans;

int main()

{

    freopen("stack.in","r",stdin);

    freopen("stack.out","w",stdout);

    scanf("%d",&n);

    f[]=;f[]=;

    for(int i=;i<=n;i++)

      for(int j=,k=i-;j<=i- && k>=;j++,k--)

        f[i]+=(f[j]*f[k])%;

    printf("%d",f[n]%);

    return ;

}

/*

模数较小是一个坑点，直接做逆元可能爆掉(模数很小许多数没有逆元)

答案是 2n!/(n!*(n+1))! 如果直接逆元,2n!预处理很可能成为零，但做了除法后答案可能不是零，就会出错。

所以7的倍数要单独考虑

这里记录了7的倍数的因子里7的幂，然后分子分母就可以加加减减了。这个题用不到。

原来逆元还可以直接搞...

*/

#include<bits/stdc++.h>

#define N 1007

using namespace std;

int n,m,d,c,r;

int fac(int n)

{

    r=;

    for(int i=;i<=n;i++)

    {

        if(i%) r=r*i%;

        else

        {

            int x=i;

            while(x%==) {x/=;c+=d;r=r*x%;}

        }

    }return r;

}

int inv(int x)

{

    for(int i=;i<;i++)

      if(i*x%==) return i;

}

int main()

{

    scanf("%d",&n);

    d=;c=;

    r=fac(*n);

    int ans=(r*inv(fac(n))%*inv(fac(n+))%)%;

    printf("%d\n",c?:ans);

    return ;

}

/*

带权并查集

维护链底，链顶，并查集找链底，并维护链的大小

合并时两个链顶链底都要维护。别忘了链底size大小改为1。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 30007

using namespace std;

int n,m,ans,cnt;

int top[N],dep[N],siz[N];

int find(int x)

{

    if(x==dep[x]) return x;

    int tmp=dep[x];

    dep[x]=find(tmp);

    siz[x]+=siz[tmp];

    return dep[x];

}

void merge(int a,int b)

{

    int r1=find(a),r2=find(b);

    dep[r1]=top[r2];

    top[r2]=top[r1];

    siz[r1]=;

}

int main()

{

    freopen("cube.in","r",stdin);

    freopen("cube.out","w",stdout);

    int x,y;char ch;

    scanf("%d",&n);

    for(int i=;i<=n;i++) top[i]=dep[i]=i;

    while(n--)

    {

        cin>>ch;

        if(ch=='M')

        {

            scanf("%d%d",&x,&y);

            merge(x,y);

        }

        else

        {

            scanf("%d",&x);find(x);

            printf("%d\n",siz[x]);

        }

    }

    return ;

} 

/*

区间dp，情况有些多需要讨论

首先连续相同的颜色为了方便要合并，记录每个块的颜色，就可以dp了

dp[l][r]表示合并这段区间的最小步数，分几种情况

这段区间是奇数(为了避免区间长度为2的情况)

1. color[l]==color[r] && tot[l]+tot[r]==2  --> dp[l][r] 可从 dp[l+1][r-1]+1 转移过来。

2. color[l]==color[r] && tot[l]+tot[r]>2   --> dp[l][r] 可从 dp[l+1][r-1] 转移过来。

3. color[l]==color[k]==color[r](k∈(l,r) && [l,k],[k,r] 为奇数)  -->可从dp[l+1][k-1]+dp[k+1][r-1]转移过来。

这段区间是偶数

普通的转移 dp[l][r] =min(dp[l][r] , dp[l][k]+dp[k+1][r]);

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 257

using namespace std;

int dp[N][N],col[N],a[N];

char s[N];

int n,m,ans;

int main()

{

    freopen("zuma.in","r",stdin);

    freopen("zuma.out","w",stdout);

    scanf("%s",s);n=strlen(s);

    a[]=;m=;

    for(int i=;i<n;i++)

    {

        if(s[i]==s[i-])

        {

            col[m]=s[i]==''?:;

            a[m]++;

        }

        else

        {

            a[++m]=;

            col[m]=s[i]==''?:;

        }

    }

    for(int len=;len<=m;len++)

    {

        for(int i=;i<=m;i++)

        {

            int j=i+len;

            if(j>= && j<=m)

            {

                dp[i][j]=*n;

                if(len==) dp[i][j]=-a[i];

                else

                {

                    for(int k=i;k<j;k++)

                      dp[i][j]=min(dp[i][k]+dp[k+][j],dp[i][j]);

                    if((j-i)%==)

                    {

                        if(a[i]+a[j]==)

                        {

                            if(col[i]==col[j])

                              dp[i][j]=min(dp[i][j],dp[i+][j-]+);

                        }

                        else

                        {

                            if(col[i]==col[j])

                              dp[i][j]=min(dp[i][j],dp[i+][j-]);

                        }

                        if(a[i]+a[j]<)

                            for(int k=i+;k<j;k+=)

                            {

                                if(a[k]==) dp[i][j]=min(dp[i+][k-]+dp[k+][j-],dp[i][j]);

                            }

                    }

                }

            }

        }

    }

    printf("%d\n",dp[][m]);

    return ;

}