Language: C++

// May this submission get accepted!

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(i, (q).size()) { cerr << (q)[i] << (i == i_len-1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
#define CHOKUDAI_ const
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using cll = DANCE_ DANCE_ CHOKUDAI_;
using  ld = long double;
using namespace std;

// モジュール
constexpr ll p = 1000000007LL;
// vector<vector<T>> のラッパクラス (プァ～)
// pの余りを取りたくない場合3箇所のコメントアウトを解除すること
template<typename T = long long>
class matrix {
    vector<vector<T>> value;
public:
    T get(size_t i, size_t j = 0) { return this->value.at(i).at(j); }
    inline size_t rows() const { return this->value.size(); }
    inline size_t cols() const { return this->value.empty() ? 0 : this->value[0].size(); }
    matrix() : value() {}
    matrix(const matrix &a) : value(a.value) {}
    matrix(size_t n, size_t m = 0) : value(n, vector<T>(m ? m : n, 0)) {}
    matrix(initializer_list<initializer_list<T>> init) : value() {
        const size_t n = init.size();
        const size_t m = [&]() {
            size_t maxm = 0;
            for (const auto& initi : init) {
                const size_t mi = initi.size();
                if (mi > maxm) maxm = mi;
            }
            return maxm;
        }();
        this->value = vector<vector<T>>(n, vector<T>(m, 0));
        size_t i = 0, j;
        for (const auto &initi : init) {
            for (const auto &v : initi) {
                this->value[i][j++] = v;
            }
            i++; j = 0;
        }
    }
    // ラムダ式の引数は(size_t, size_t)、返り値はTとすること (まあ整数型なら大丈夫でしょ)
    template <class LAMBDA>
    static matrix<T> map(const size_t n, const size_t m, LAMBDA f) {
        matrix<T> r(n, m);
        for (size_t i = 0; i < n; i++) {
            for (size_t j = 0; j < m; j++) {
                r.value[i][j] = f(i, j);
            }
        }
        return r;
    }
    static matrix eye(const size_t n) {
        matrix<T> r(n);
        for (size_t i = 0; i < n; i++) r.value[i][i] = 1;
        return r;
    }
    matrix<T> operator+ (const matrix<T> &a) {
        if (this->rows() != a.rows()) exit(EXIT_FAILURE);
        if (this->cols() != a.cols()) exit(EXIT_FAILURE);
        const size_t n = this->rows();
        const size_t m = this->cols();
        return matrix<T>::map(n, m, [&](size_t i, size_t j) {
            // return this->value[i][j] + a.value[i][j];
            return (this->value[i][j] + a.value[i][j]) % p;
        });
    }
    matrix<T> operator- (const matrix<T> &a) {
        if (this->rows() != a.rows()) exit(EXIT_FAILURE);
        if (this->cols() != a.cols()) exit(EXIT_FAILURE);
        const size_t n = this->rows();
        const size_t m = this->cols();
        return matrix<T>::map(n, m, [&](size_t i, size_t j) {
            // return this->value[i][j] - a.value[i][j];
            return (this->value[i][j] + p - a.value[i][j]) % p;
        });
    }
    matrix<T> operator* (const matrix<T> &a) {
        if (this->cols() != a.rows()) exit(EXIT_FAILURE);
        const size_t n = this->rows();
        const size_t m = this->cols();
        const size_t q = a.cols();
        return matrix<T>::map(n, q, [&](size_t i, size_t j) {
            T term = 0;
            for (size_t k = 0; k < m; k++)
                // term += this->value[i][k] * a.value[k][j];
                (term += this->value[i][j] * a.value[i][j]) %= p;
            return term;
        });
    }
    matrix<T>& operator+= (const matrix<T> &a) {
        matrix<T> r = *this + a;
        this->value.swap(r.value);
        return *this;
    }
    matrix<T>& operator-= (const matrix<T> &a) {
        matrix<T> r = *this - a;
        this->value.swap(r.value);
        return *this;
    }
    matrix<T>& operator*= (const matrix<T> &a) {
        matrix<T> r = *this * a;
        this->value.swap(r.value);
        return *this;
    }
    matrix<T> transpose() {
        const size_t n = this->rows();
        const size_t m = this->cols();
        return matrix<T>::map(m, n, [&](size_t i, size_t j) {
            return this->value[j][i];
        });
    }
    matrix<T> pow(long long int n) {
        if (n == 0) {
            return matrix<T>::idtm(n);
        } else if (n == 1) {
            return *this;
        } else {
            matrix temp = this->pow(n / 2);
            return n % 2 == 0 ? temp * temp : temp * temp * *this;
        }
    }
};

// 処理内容
int main() {
    
    matrix<ll> a_a = {
        {1, 0, 0, 0},
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {1, 0, 0, 1}
    };
    matrix<ll> a_b = {
        {1, 1, 0, 0},
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1}
    };
    matrix<ll> a_c = {
        {1, 0, 0, 0},
        {0, 1, 1, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1}
    };
    matrix<ll> a_any = a_a + a_b + a_c;
    
    matrix<ll> x0 = {{0, 0, 0, 1}};
    matrix<ll> a = matrix<ll>::eye(4);

    string s; cin >> s;
    map<char, matrix<ll>&> lmap;
    lmap['A'] = a_a;
    lmap['B'] = a_b;
    lmap['C'] = a_c;
    lmap['?'] = a_any;
    REP(i, s.size()) {
        a *= lmap[s[i]];
    }
    matrix<ll> x = x0 * a;
    cout << x.get(0, 2) << endl;
    
}

Compiler output:
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:7:
/usr/include/c++/14/tuple: In instantiation of 'std::pair<_T1, _T2>::pair(std::tuple<_Args1 ...>&, std::tuple<_Args2 ...>&, std::_Index_tuple<_Indexes1 ...>, std::_Index_tuple<_Indexes2 ...>) [with _Args1 = {char&&}; long unsigned int ..._Indexes1 = {0}; _Args2 = {}; long unsigned int ..._Indexes2 = {}; _T1 = const char; _T2 = matrix<long long int>&]':
/usr/include/c++/14/tuple:2879:63:   required from 'std::pair<_T1, _T2>::pair(std::piecewise_construct_t, std::tuple<_Args1 ...>, std::tuple<_Args2 ...>) [with _Args1 = {char&&}; _Args2 = {}; _T1 = const char; _T2 = matrix<long long int>&]'
 2879 |              typename _Build_index_tuple<sizeof...(_Args2)>::__type())
      |                                                                      ^
/usr/include/c++/14/bits/new_allocator.h:191:4:   required from 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::pair<const char, matrix<long long int>&>; _Args = {const std::piecewise_construct_t&, std::tuple<char&&>, std::tuple<>}; _Tp = std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> >]'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<const char, matrix<long long int>&>; _Args = {const std::piecewise_construct_t&, std::tuple<char&&>, std::tuple<>}; _Tp = std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> >; allocator_type = std::allocator<std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> > >]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:593:32:   required from 'void std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_construct_node(_Link_type, _Args&& ...) [with _Args = {const std::piecewise_construct_t&, std::tuple<char&&>, std::tuple<>}; _Key = char; _Val = std::pair<const char, matrix<long long int>&>; _KeyOfValue = std::_Select1st<std::pair<const char, matrix<long long int>&> >; _Compare = std::less<char>; _Alloc = std::allocator<std::pair<const char, matrix<long long int>&> >; _Link_type = std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> >*]'
  593 |               _Alloc_traits::construct(_M_get_Node_allocator(),
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
  594 |                                        __node->_M_valptr(),
      |                                        ~~~~~~~~~~~~~~~~~~~~
  595 |                                        std::forward<_Args>(__args)...);
      |                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:610:21:   required from 'std::_Rb_tree_node<_Val>* std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {const std::piecewise_construct_t&, std::tuple<char&&>, std::tuple<>}; _Key = char; _Val = std::pair<const char, matrix<long long int>&>; _KeyOfValue = std::_Select1st<std::pair<const char, matrix<long long int>&> >; _Compare = std::less<char>; _Alloc = std::allocator<std::pair<const char, matrix<long long int>&> >; _Link_type = std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> >*]'
  610 |           _M_construct_node(__tmp, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1633:32:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Auto_node::_Auto_node(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&, _Args&& ...) [with _Args = {const std::piecewise_construct_t&, std::tuple<char&&>, std::tuple<>}; _Key = char; _Val = std::pair<const char, matrix<long long int>&>; _KeyOfValue = std::_Select1st<std::pair<const char, matrix<long long int>&> >; _Compare = std::less<char>; _Alloc = std::allocator<std::pair<const char, matrix<long long int>&> >]'
 1633 |             _M_node(__t._M_create_node(std::forward<_Args>(__args)...))
      |                     ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:2460:13:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_emplace_hint_unique(const_iterator, _Args&& ...) [with _Args = {const std::piecewise_construct_t&, std::tuple<char&&>, std::tuple<>}; _Key = char; _Val = std::pair<const char, matrix<long long int>&>; _KeyOfValue = std::_Select1st<std::pair<const char, matrix<long long int>&> >; _Compare = std::less<char>; _Alloc = std::allocator<std::pair<const char, matrix<long long int>&> >; iterator = std::_Rb_tree<char, std::pair<const char, matrix<long long int>&>, std::_Select1st<std::pair<const char, matrix<long long int>&> >, std::less<char>, std::allocator<std::pair<const char, matrix<long long int>&> > >::iterator; const_iterator = std::_Rb_tree<char, std::pair<const char, matrix<long long int>&>, std::_Select1st<std::pair<const char, matrix<long long int>&> >, std::less<char>, std::allocator<std::pair<const char, matrix<long long int>&> > >::const_iterator]'
 2460 |         _Auto_node __z(*this, std::forward<_Args>(__args)...);
      |                    ^~~
/usr/include/c++/14/bits/stl_map.h:532:37:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](key_type&&) [with _Key = char; _Tp = matrix<long long int>&; _Compare = std::less<char>; _Alloc = std::allocator<std::pair<const char, matrix<long long int>&> >; mapped_type = matrix<long long int>&; key_type = char]'
  532 |           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  533 |                                         std::forward_as_tuple(std::move(__k)),
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  534 |                                         std::tuple<>());
      |                                         ~~~~~~~~~~~~~~~
a.cc:187:13:   required from here
  187 |     lmap['A'] = a_a;
      |             ^
/usr/include/c++/14/tuple:2890:9: error: value-initialization of reference type 'matrix<long long int>&'
 2890 |         second(std::forward<_Args2>(std::get<_Indexes2>(__tuple2))...)
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/tuple: In instantiation of 'std::pair<_T1, _T2>::pair(std::tuple<_Args1 ...>&, std::tuple<_Args2 ...>&, std::_Index_tuple<_Indexes1 ...>, std::_Index_tuple<_Indexes2 ...>) [with _Args1 = {const char&}; long unsigned int ..._Indexes1 = {0}; _Args2 = {}; long unsigned int ..._Indexes2 = {}; _T1 = const char; _T2 = matrix<long long int>&]':
/usr/include/c++/14/tuple:2879:63:   required from 'std::pair<_T1, _T2>::pair(std::piecewise_construct_t, std::tuple<_Args1 ...>, std::tuple<_Args2 ...>) [with _Args1 = {const char&}; _Args2 = {}; _T1 = const char; _T2 = matrix<long long int>&]'
 2879 |              typename _Build_index_tuple<sizeof...(_Args2)>::__type())
      |                                                                      ^
/usr/include/c++/14/bits/new_allocator.h:191:4:   required from 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::pair<const char, matrix<long long int>&>; _Args = {const std::piecewise_construct_t&, std::tuple<const char&>, std::tuple<>}; _Tp = std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> >]'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<const char, matrix<long long int>&>; _Args = {const std::piecewise_construct_t&, std::tuple<const char&>, std::tuple<>}; _Tp = std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> >; allocator_type = std::allocator<std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> > >]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:593:32:   required from 'void std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_construct_node(_Link_type, _Args&& ...) [with _Args = {const std::piecewise_construct_t&, std::tuple<const char&>, std::tuple<>}; _Key = char; _Val = std::pair<const char, matrix<long long int>&>; _KeyOfValue = std::_Select1st<std::pair<const char, matrix<long long int>&> >; _Compare = std::less<char>; _Alloc = std::allocator<std::pair<const char, matrix<long long int>&> >; _Link_type = std::_Rb_tree_node<std::pair<const char, matrix<long long int>&> >*]'
  593 |               _Alloc_traits::construct(_M_get_Node_allocator(),
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
  594 |                                        __node->_M_valptr(),
      |                                        ~~~~~~~~~~~~~~~~~~~~
  595 |                                        std::forward<_Args>(__args)...);
      |                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:610:21:   required from 'std::_Rb_tree_node<_Val>* std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {const std::piecewise_construct_t&, std::tuple<const char&>, std::tuple<>}; _Key = char; _Val = std::pair<const char, matrix<long long int>&>; _KeyOfValue = std::_Select1