喵喵喵
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小喵捡了一只猫，取名叫小小喵。
小喵有一个技能，会把一个字符串中所有的小写字母'n'后面加两个字母'y'和'a'。
例如，对于字符串"nynnya"，小喵发动技能后会变成"nyaynyanyaya"。
小小喵有一个技能，会把一个字符串中所有的子串"ya"变成字符"n"。
例如，对于字符串"nynnya"，小小喵发动技能后会变成"nynnn"。
已知一个字符串初始为 ，小喵和小小喵共发动了 次技能。
小喵想知道字符串最终长度是多少？请对 取模。

输入描述:

第一行是一个只包含小写字母的字符串  。 
第二行为一个正整数 ，代表技能发动的轮数。
第三行为一个长度为  的、仅包含大写字母'N'和小写字母'n'的字符串，代表小喵和小小喵的操作。'N'代表小喵操作一次，'n'代表小小喵操作一次。

输出描述:

输出最终字符串长度对  取模的值。
示例1

输入

复制 
nyany
2
Nn

输出

复制 
6

说明

最开始的字符串是nyany。
小喵操作一次，字符串变成nyayanyay
小小喵操作一次，字符串变成nnnnny。
最终长度为6。