小天的子序列

题目描述

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

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

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

- 题目中的字符均为小写字母。

- 题目所求子序列不要求本质不同。

答案对998244353取模。

输入描述

第一行一个正整数n(1≤n≤500)表示字符串的长度。

第二行一个字符串s。

第三行一个正整数m(1≤m≤10^5)表示询问次数。

接下来m行，每行两个字符ch1,ch2和一个正整数len(2≤len≤n)描述一个询问。

输出描述

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