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

Обмеження: 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.