• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

گزارشاتی پنهانی از تقلب‌های حلی سه‌ای ها در کنکور رسیده‌است. متن تقلب‌ها یک رشته است که متاسفانه در دست ما نیست اما از عملیات‌های رمزنگاری آن خبر داریم. هر عملیات رمز نگاری یک حرف را به حرف دیگری تبدیل می‌کند.

لازم به ذکر است که اگر حرفی وجود داشت که به هیچ حرف دیگری تبدیل نشده بود. در رشته هم هیچ تغییری نمی‌کند.

تعداد این عملیات ها $n$‌تا است.

ما فقط می‌دانیم متن تقلب‌ها رشته‌ای یکّه است. یکّه به این معناست که اگر متن اصلی گزارش برابر رشته‌ی $s$ و متن رمز گشایی شده (که با انجام پشت سر هم عملیات‌ها بدست آمده) برابر رشته‌ی $c$‌باشد. بتوانیم از $c$ با انجام دادن برعکس عملیات‌ها به $s$ برسیم.

انجام برعکس عملیات‌ها به این معناست که اولاً از عملیات آخر شروع کنیم و تا عملیات اول برویم و دوماً اگر در عملیاتی ما $'a'$ را به $'b'$ تبدیل کردیم در برعکس آن, $'b'$ را به $'a'$ تبدیل خواهیم کرد. برای مثال اگر این دو تبدیل ، تمام عملیات‌های ما باشند:

a b
b c

این دو تبدیل(عملیات) برعکس آن خواهد بود:

c b
b a

برای مثال بالا $"aa"$ یک رشته‌ی یکه به طول دو محسوب می‌شود. زیرا اگر عملیات‌های اصلی روی آن انجام شود حاصل $"cc"$ است و اگر عملیات‌های برعکس روی $"cc"$‌ اعمال شود ما دوباره به همان $"aa"$ می‌رسیم. و $"bb"$ یک رشته‌ی یکه نیست! چون اگر عملیات‌های درست روی آن اعمال شود $"cc"$ حاصل می‌شود و همانطور که گفتیم $"cc"$ در انجام دادن برعکس عملیات‌ها به $"aa"$ ختم می‌شود.

می‌خواهیم ببینیم این تقلب‌ها(رشته‌های یکّه) چند حالت مختلف به طول مشخص‌شده دارند؟؟

اما از بد حادثه تعدادی از عملیات‌های پشت سر هم اشتباهاً اضافه شده است. فلذا $q$ پرسش از شما می‌شود به این شکل که برای هر پرسش سه عدد $t, l, r$ داده می‌شود و شما باید باقی مانده تعداد رشته‌های یکه به طول $t$ بر $1e9+7$ را با فرض این که عملیات‌های $l$ تا $r$ حذف شده‌اند چاپ کنید.

ورودی

در خط اول ورودی عدد $n$ می‌آید. سپس در $n$ خط بعدی در هر خط یک جفت حرف می‌آید که نشان دهنده عملیات هاست. در خط $n + 2$ ام عدد $q$ می‌آید که تعداد پرسش هاست و در نهایت $q$ خط که هر کدام نشانگر یک پرسش است.

$$1 \leq n,q \leq 200\ 000$$

$$1 \leq t \leq 200\ 000$$

$$1\leq l \leq r \leq n$$

تمامی کاراکتر‌های ورودی از حروف لاتین کوچک تشکیل شده‌اند.

خروجی

در $q$ خط خروجی به ازای هر پرسش جواب آن را چاپ نمایید.

مثال

ورودی نمونه ۱

2
a b
b c
3
1 1 2
1 1 1
1 2 2

خروجی نمونه ۱

26
25
25

در اولین پرسش به دلیل وجود نداشتن هیچ عملیاتی می‌توان از هر حرفی استفاده کرد.

در دومین پرسش نمی‌توان از $"c"$ به عنوان رشته‌ی ورودی استفاده کرد زیرا بعد از عملیات، همان $"c"$ ماند و اگر مرحله برعکس عملیات را انجام دهیم تبدیل به $"b"$ خواهد شد.

در سومین پرسش نیز نمی‌توان از $"b"$ به عنوان رشته‌ی ورودی استفاده کرد.

ورودی نمونه ۲

7
c f
e f
c c
e d
f b
f c
f b
4
1 3 5
2 3 5
1 2 6
1 4 4

خروجی نمونه ۲

23
529
24
23