PAIRINGS = {
    '{' : '}',
    '[' : ']',
    '(' : ')',
    '<' : '>'
}

def valid_parentheses_count(s: str) -> int:
    stack = []
    s = list(s)
    memo = {}
    res = impl(s, 0, stack, memo)
    print("Result: ", res, "(", "".join(s), ")")


def impl(s, index, stack, memo):
    if index >= len(s):
        return 1 if len(stack) == 0 else 0
    if len(stack) > len(s) - index:
        return 0
    curr_char = s[index]
    if curr_char == '?':
        total = 0
        for sel_char in list(PAIRINGS.keys()) + list(PAIRINGS.values()):
            if index < 3 and len(s) > 15:
                print(index, sel_char)
            s[index] = sel_char
            total += impl(s, index, stack, memo)
        s[index] = '?'
        return total
    elif curr_char in PAIRINGS:
        stack.append(curr_char)
        res = impl(s, index+1, stack, memo)
        stack.pop()
        return res
    else:
        if len(stack) == 0:
            return 0
        matching = stack.pop()
        if PAIRINGS[matching] != curr_char:
            res = 0
        elif ("".join(stack), index) in memo:
            res = memo[("".join(stack), index)]
        else:
            res = impl(s, index+1, stack, memo)
            memo[("".join(stack), index)] = res
        stack.append(matching)
        return res

# Test cases
valid_parentheses_count("?[??")  # Output: 4
valid_parentheses_count("?)??")  # Output: 4
valid_parentheses_count("?[??")  # Output: 4
valid_parentheses_count("??")
valid_parentheses_count("????")
valid_parentheses_count("??????")
valid_parentheses_count("????????")
valid_parentheses_count("??????????")
valid_parentheses_count("????????????")
valid_parentheses_count("??????????????")
valid_parentheses_count(")???")  # Output: 0
valid_parentheses_count("?<????????????)??]???????}??")