李享有一个长度为n的字符串，字符串只包括'X','C','P' 这三种字符。

bitwim给李享出了Q个询问，每次询问给两个正整数x,y，区间为[min(x,y),max(x,y)],问在这个区间中有多少个子序列为XCPC。

一个字符串a是另一个字符串b的子序列，满足a可以通过删除b任意位置的一些字符获得。

因为存在多组询问，所以李享只想知道所有询问的答案在模$1e9+7$的结果。

第一行包括$n,Q(1 <= n, Q <= 2e6)$，代表字符串$s$的长度和询问次数。

第二行包括一个字符串$s$。

接下来Q行，每行包括两个正整数$x,y(1 <= x,y <= n)$。

只有一行包含一个整数，表示每个查询的答案之和，模$1e9+7$。