For a string of digits , let c_0, c_{01}, c_{012} and c_{0123} be the numbers of its subsequences equal to 0, 01, 012 and 0123; the number of climbs is c_{0123}. Appending one digit changes exactly one of the counters, and only by adding another one:
Indeed, a new occurrence of 01 must end at the new 1, and its 0 is any of the c_0 earlier zeros; the other digits are similar.
Key observation. We only need c_{0123} \bmod 4, and since the updates use nothing but additions, all four counters can be kept modulo from the start: reducing modulo commutes with addition, so the reduced counters after every prefix are exactly the true counters reduced modulo . The true counts are huge (the number of climbs can exceed 2^{64}), but they are never needed.
So the whole string is processed by an automaton with 4^4 = 256 states (c_0, c_{01}, c_{012}, c_{0123}) \bmod 4, starting in (0,0,0,0). Let be the number of ways to fill the ? of the current prefix so that it ends in state , modulo . A fixed digit moves each to the state given by its update; a ? adds to each of the four successors of . The answer is the sum of over the states with c_{0123} \equiv 0 \pmod 4. Only the current layer of has to be stored; precomputing the successor of every state for every digit keeps the inner loop simple.
All states are needed: for instance, keeping c_0 only modulo is wrong, because c_0 is later multiplied by the number of 123 after it, which may be odd.
The complexity is O(256 \cdot 4 \cdot |s|) per test case, with memory.