小Why拿到了一个密码长度为 的密码锁，这个密码锁可输入内容无限，并只对最后输入的 位字符进行检测，检测正确时密码锁会解锁一次，同时清空包含检测正确字符串在内的之前的所有字符。 小Why输入了一个长度为 的字符串 后，密码锁一共解锁了 次，请你告诉他有多少种密码是可能正确的。

输入描述:

第一行包含三个整数 ，表示字符串  的长度，密码长度和解锁次数。第二行包含一个长度为的字符串 ，保证字符串  中只含有  的数字。

输出描述:

输出一个整数，表示有多少种密码是可能正确的。