小天的子序列

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

题目描述

小冰老是搞不清楚子串和子序列的区别，小天想要帮助小冰区分子串和子序列，小天告诉小冰，子串是连续的，子序列不一定连续，在一个字符串中，如果确定了子串的首和尾，那么子串就确定了。而子序列却不一定。

小冰在小天的帮助下，终于学会了。但是现在她遇到了一个难题，想请你帮助她解决一下。

小冰给你一个字符串， $m$ 次询问，每次询问字符串中有多少个以 $ch_1$ 开头，以 $ch_2$ 结尾的长为 $len$ 的子序列。

- 题目中的字符均为小写字母。
- 题目所求子序列不要求本质不同。

答案对 $998244353$ 取模。

输入描述:

第一行一个正整数  表示字符串的长度。

第二行一个字符串 。

第三行一个正整数  表示询问次数。

接下来  行，每行两个字符  和一个正整数  描述一个询问。

输出描述:

共  行，每行一个整数表示询问的子序列数量。

示例1

输入

复制

9
abcxayidy
2
x y 4
x y 2

输出

复制

6
2