时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
本题与hard版区别只在于 
的数据范围不同，并且保证easy版的测试用例是hard版的测试用例的子集。
嘤嘤有一个只由小写字母组成的字符串，她希望把这个字符串变得跟她一样可爱。
嘤嘤有一个魔法，可以将字符串中的一个小写字母变成一个小写字母（可以和原字母相同），这个魔法可以使用 次。
一个字符串的可爱值定义为这个字符串中含有的 'y' , 'k' , 'a' , 'w' , 'i' 这五种字母的数量，例如"yykawaii"的可爱值是8，"zjkgg"的可爱值是1，而"qcjj"的可爱值……
嘤嘤有一个魔法，可以将字符串中的一个小写字母变成一个小写字母（可以和原字母相同），这个魔法可以使用
一个字符串的可爱值定义为这个字符串中含有的 'y' , 'k' , 'a' , 'w' , 'i' 这五种字母的数量，例如"yykawaii"的可爱值是8，"zjkgg"的可爱值是1，而"qcjj"的可爱值……
由于嘤嘤正在被qcjj追杀，所以嘤嘤留下的魔法只能随机使用了（随机将字符串中的一个小写字母随机变成一个小写字母，可能和原字母相同）。
现在，嘤嘤给出字符串和 ，她想知道她的字符串在随机使用 次魔法后，可爱值的期望是多少。
现在，嘤嘤给出字符串和
PS：qcjj其实非常可爱哦！（绝对不是qcjj要我加的）附一张qcjj头像同款的白毛萝莉图。
世界名画——《喂！不许这样盯着我看，你这个死萝莉控！！！》（德莉莎·阿波卡利斯）（图片加载失败）
输入描述:
第一行给出两个整数，分别表示嘤嘤的字符串的长度和可以使用魔法次数。
第二行给出一个长度为的只由小写字母组成的字符串
，表示嘤嘤的字符串。
输出描述:
输出可爱值的期望对取模的结果。