Щасливі підпослідовності

Обмеження: 2 сек., 512 МіБ

Марічка любить щасливі рядки — непорожні рядки, що містять тільки букви l, u, c, k, y.

У магазині продається рядок $s$ довжини $n$. Зеник вирішив в $i$-ту хвилину літа купити підрядок $s[l_i..r_i]$ й утворити щасливий рядок, щоб подарувати його Марічці. Рядок $s$ є в магазині в багатьох екземплярах, тому Зеник щоразу купує підрядок з іншого екземпляра.

Для кожного купленого підрядка порахуйте, скільки унікальних щасливих рядків він може отримати з нього, видаливши деякі (можливо, жоден) символи.

Оскільки кількість унікальних щасливих підпослідовностей може бути великою, то виведіть її за модулем простого числа $10^9 + 7$.

Вхідні дані

У першому рядку задано два цілих числа $n$ і $m$ — довжина рядка в магазині та кількість хвилин, коли Зеник купував підрядки.

У другому рядку задано рядок $s$ довжини $n$ — рядок, що продається в магазині.

У наступних $m$ рядках задано по два цілих числа $l_i, r_i$ — підрядок, який купив Зеник у магазині в $i$-ту хвилину літа.

Вихідні дані

У кожному з $m$ рядків виведіть ціле число — кількість унікальних щасливих підпослідовностей у підрядку $s[l_i .. r_i]$ за модулем $10^9 + 7$.

Обмеження

$1 \le n, m \le 10^5$,

$1 \le l \le r \le n$,

рядок $s$ містить лише маленькі англійські літери.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 3 luuby 1 3 2 4 1 5	5 2 11

Примітки

Для підрядка $s[1 .. 3]$ є такі унікальні підпослідовності: l, u, lu, uu, luu.

Для підрядка $s[2 .. 4]$ є такі унікальні підпослідовності: u, uu.

Для підрядка $s[1 .. 5]$ є такі унікальні підпослідовності: l, u, y, lu, ly, uu, uy, luu, luy, uuy, luuy.