问题 A: count buct
内存限制：1024 MB
时间限制：2.500 S
评测方式：文本比较
命题人：
提交：9
解决：3
题目描述
给你一个只包含小写字母的字符串 $S$ ，共有 $q$ 次询问，每次询问一个区间 $[l, r]$ 范围内 "buct" 子序列的个数（注意答案可能很大需要对 $10^9+7$ 取模）。
输入
第一行一个整数 $1 \le n \le 10^5$ 代表字符串 $S$ 的长度
第二行为字符串 $S$
第三行一个整数 $1 \le q \le 10^5$ 代表询问个数
接下来 $q$ 行每行两个整数 $1 \le l \le r \le n$
第二行为字符串 $S$
第三行一个整数 $1 \le q \le 10^5$ 代表询问个数
接下来 $q$ 行每行两个整数 $1 \le l \le r \le n$
输出
对于每个询问请输出一个整数代表答案对 $10^9+7$ 取模后的结果并换行
样例输入 复制
17
buczubutbucctfbuc
3
2 15
9 13
1 5样例输出 复制
6
2
0