Sizga N ta belgidan iborat satr berilgan. Satr kichik lotin harflaridan yoki ”?”(so'roq) belgisidan tashkil topishi mumkin. Bundan  tashqari sizga M ta ma’lumot beriladi, har bitta ma’lumot ikkita x, y sonlaridan tashkil topgan bo’lib, bu ma’lumot satrning x va y indeksdagi belgilari bir xil bo’lishi zarurligini anglatadi. Sizning vazifangiz shu ma’lumotlar yordamida berilgan satrdagi so'roqlar o’rniga lotin harflarini qo’ygan holda, berilgan satrdan necha xil polindrom satr hosil qilish mumkinligini hisoblashdir.

Kiruvchi ma’lumotlar: Birinchi satrda N va M sonlari (1 ≤ N ≤ 1000000, 1 ≤ M ≤ 1000000). Ikkinchi satrda N ta belgidan tashkil topgan satr beriladi. Keyingi M ta satrda ikkitadan son, x va y natural sonlari (1 ≤ x, y ≤ N ). Berilgan satrda faqat kichik lotin harflari va “?”(so'roq) belgisidan tashqari belgilar uchramasligi kafolatlanadi.

Chiquvchi ma’lumotlar: masala javobini 1,000,000,007(10⁹+7) ga bo’lgandagi qoldiqini hisoblang.