C. Ваня ба шошго

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Гудамжаар алхаж байгаад Ваня "Hide&Seek" гэх нэгэн шошго харжээ. Тэрээр программист учраас битийн AND үйлдэл болох $&$-ыг эдгээр 2 үгийн $64$ суурьтай бүхэл тоон илэрхийллүүд дээр хэрэглэн шинэ үг үүсгэжээ. Одоо Ваня ямар нэгэн $s$ тэмдэгт мөрийн тухай бодож байгаа бөгөөд тэрээр битийн AND үйлдлийнх утга $s$-тэй тэнцүү байх $|s|$ урт бүхий ($s$-ын урт) хос үгүүдийн тоог мэдэхийг хүсжээ. Уг тоо нь хэтэрхий том тоо байж болох учраас хариултыг $10^{9} + 7$ модулаар бодож хэвлэнэ үү.

Тэмдэгт мөрийг $64$ суурьтай тооллын системийн тоо болгон илэрхийлэхийн тулд Ваня дараах дүрмүүдийг мөрдөнө:

  • '$0$'-ээс '$9$' хүртэлх цифрүүд нь $0$-оос $9$ хүртэлх бүхэл тоонуудад харгалзана;
  • '$A$'-аас '$Z$' хүртэлх үсгүүд нь $10$-аас $35$ хүртэлх бүхэл тоонуудад харгалзана;
  • '$a$'-аас '$z$' хүртэлх үсгүүд нь $36$-аас $61$ хүртэлх бүхэл тоонуудад харгалзана;
  • '$-$' үсэг нь $62$ гэсэн бүхэл тоонд харгалзана;
  • '$_$' үсэг нь $63$ гэсэн бүхэл тоонд харгалзана.

Оролт

Оролтод ганц мөр өгөгдөх ба уг мөрөнд Англи жижиг том үсгүүд, цифрүүд, '$-$' болон '$_$' тэмдэгтүүдээс тогтох $s$ ($1 ≤ |s| ≤ 100 000$) тэмдэгт мөр өгөгдөнө.

Гаралт

Битийн AND үйлдлийнх нь утга $s$-тэй тэнцүү байх боломжит хос үгүүдийн тоог $10^{9} + 7$ модулаар бодсон утгыг хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
z
Гаралт
3
Оролт
V_V
Гаралт
9
Оролт
Codeforces
Гаралт
130653412

Тэмдэглэл

Битийн AND үйлдлийн тайлбарыг Wikipedia дээрх харгалзах нийтлэлээс харахыг зөвлөж байна.

Эхний жишээнд $3$ боломжит хариулт байна:

  1. $z&_ = 61&63 = 61 = z$
  2. $_&z = 63&61 = 61 = z$
  3. $z&z = 61&61 = 61 = z$
Сэтгэгдлүүдийг ачааллаж байна...