Masala #0142

Bilag’on palindrom satrlarni juda yaxshi ko’radi. Shuning uchun u ayrim so’zlarning harflaridan foydalangan holda hosil qilish mumkin bo’lgan eng uzun palindromlarni yasaydi. Masalan bobo so’zidan u obbo yoki boob so’zlarini, robocontest so’zidan esa otrto, torot, otbto, tobot, ototo, tooot,  otcto, tocot, otnto, tonot, oteto, toeot, otsto, tosot so’zlarini hosil qila oladi.

INPUT.TXT kirish faylining dastlabki satrida kichik lotin harflaridan iborat S(1 ≤ |S| ≤ 10⁵) satri kiritiladi, ikkinchi satrda T(1 ≤ T ≤ 10⁵) butun son va keyingi T ta qatorda so’rov beriladi. Har bir so’rovda L va R(1 ≤ L ≤ R ≤ |S|) sonlari kiritiladi.

OUTPUT.TXT chiqish faylida har bir so’rov uchun alohida qatorda agarda Bilag’onga S satrning [L,…,R] qism satri berilganida u jami necha xil eng uzun palindrom satr hosil qilishi mumkinligini chop eting. Bu son juda katta bo’lishi mumkin, shuning uchun siz bu sonning 10⁹+7 ga bo’lgandagi qoldig’ini chop eting.