不断复制的记录

题目描述

初始记录是字符串 w。第 i 轮把当前完整记录复制两份，在两份之间插入一个字符 c_i，即形成“旧记录、c_i、旧记录”。完成 n 轮后，求目标字符出现多少次。大小写问题不存在，所有字符都是小写英文字母。

输入格式

第一行 n 和目标字符；第二行 w；n>0 时第三行给出长度为 n 的插入字符序列，n=0 时没有第三行。

输出格式

输出目标字符的出现次数。

样例 1

输入

2 a
ab
ca

输出

5

说明

初始一个 a，第一轮为 2 个，第二轮为 2×2+1=5 个。

样例 2

输入

0 b
aaa

输出

0

说明

没有执行复制，原记录中没有 b。

数据范围

• 0≤n≤50；1≤|w|≤5；答案在 long long 范围内。