描述

一天,刚学OI的xh童鞋正在水贴吧。突然他看到了这样一段C++程序:
 
string s[201]; // 定义一个可存储201个字符串的数组
s[1]="b"; s[2]="a"; // 给前两个字符串赋值
cin>>n; // 读入n
for(int i=3;i<=n;i++) s[i]=s[i-1]+s[i-2]; // +表示连接两个字符串
cout<<s[n]; // 输出第n个字符串
 
于是不假思索的xh迅速把它复制到IDE里补全其它部分编译了一下……结果可想而知……
望着满屏幕的字符,xh的目光停留在了其中的一段上。他突然想知道:这段字符在屏幕上这个字符串中出现了多少次?

输入格式

第一行一个长度不超过30的只含有a和b的字符串,表示xh看到的那段字符。
第二行一个整数n,1<=n<=30。

输出格式

xh看到的那段字符在字符串s[n]中出现的次数。

样例输入

aba
6    

样例输出

3