İri buynuzlu mal-qaranın genetikası

Fermer Con genomların sıralanmasından sonra onların redaktəsinə başladı! Bildiyimiz kimi, genom A, C, G və T hərflərindən ibarət bir sıra ilə təmsil olunur. Fermer Conun nəzərdən keçirdiyi genomun maksimal uzunluğu 10^5-dir.

Fermer Con bir genomla başlayır və onu aşağıdakı addımlarla redaktə edir:

• Genomu ardıcıl eyni simvollar arasında bölün.

• Hər bir alınan alt sətiri tərsinə çevirin.

• Tərsinə çevrilmiş alt sətirləri eyni ardıcıllıqla birləşdirin.

Məsələn, əgər Fermer Con genomu AGGCTTT ilə başlasa, o, aşağıdakı addımları yerinə yetirəcək:

• Genomu ardıcıl G və T arasında bölərək AG | GCT | T | T əldə edin.

• Hər bir alt sətiri tərsinə çevirərək GA | TCG | T | T əldə edin.

• Alt sətirləri birləşdirərək GATCGTT əldə edin.

Təəssüf ki, genomun redaktəsindən sonra Fermer Conun kompüteri sıradan çıxdı və o, ilkin olaraq başladığı genom ardıcıllığını itirdi. Bundan əlavə, redaktə edilmiş genomun bəzi hissələri zədələndi - onlar sual işarələri ilə əvəz olundu.

Redaktə edilmiş genom ardıcıllığını bilə-bilə, Fermer Cona mümkün ilkin genomların sayını 10^9 + 7 moduluna görə müəyyən etməyə kömək edin.

Giriş Məlumatları

Hər bir simvolu A, G, C, T və ya ? olan boş olmayan bir sıra.

Çıxış Məlumatları

Mümkün ilkin genomların sayını 10^9 + 7 moduluna görə çıxarın.

Nümunə 1

Sual işarəsi A, G, C və ya T ola bilər.

Nümunə 2

AGGCTTT-dən başqa iki mümkün ilkin genom mövcuddur, yuxarıda təsvir edilmişdir.

AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT

TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT