Lucky Subsequences

Limits: 2 sec., 512 MiB

Marichka likes lucky strings – the non-empty strings which contain only letters l, u, c, k, y.

The string \(s\) of length \(n\) is sold in the store. Zenyk decided to buy the substring \(s[l_i..r_i]\) in the \(i\)-th minute of summer, make a lucky string of it and gift this lucky string to Marichka. There are many instances of \(s\) in the store, so every time Zenyk buys substring of a new instance.

For each bought substring count how many unique lucky strings can be obtained from it by deleting several (possibly none) characters.

As the number of unique lucky subsequences can be large, output it modulo prime number \(10^9+7\).

Input

The first line contains two integers \(n\) and \(m\) – length of the string in the store and number of minutes when Zenyk was buying substrings.

The second line contains the string \(s\) of length \(n\) which is sold in the store.

Each of the next \(m\) lines contains two integers \(l_i\) and \(r_i\) which define a bought substring.

Output

Output \(m\) lines, each containing an integer – number of unique lucky subsequences in the substring \(s[l_i .. r_i]\) modulo \(10^9+7\).

Constraints

\(1 \le n, m \le 10^5\),

\(1 \le l \le r \le n\),

the string \(s\) contains only small Latin letters.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 3 luuby 1 3 2 4 1 5	5 2 11

Notes

The substring \(s[1 .. 3]\) contains such lucky subsequences: l, u, lu, uu, luu.

The substring \(s[2 .. 4]\) contains such lucky subsequences: u, uu.

The substring \(s[1 .. 5]\) contains such lucky subsequences: l, u, y, lu, ly, uu, uy, luu, luy, uuy, luuy.