def flatten_substitution_choices(subs_choices):
    """
    For a given dict {expr: (expr1, expr2)} returns a list of all possible substitution arising from choosing to subs
    expr by expr1 or expr2.
    """
    subs_choices = subs_choices.copy()
    if not subs_choices:
        return [{}]

    result = []
    expr = next(iter(subs_choices.keys()))
    choice1, choice2 = subs_choices.pop(expr)
    remaining_choices_flat = flatten_substitution_choices(subs_choices)
    for c in remaining_choices_flat:
        c1 = c.copy()
        c1[expr] = choice1
        result.append(c1)
        if choice1 != choice2:
            c2 = c.copy()
            c2[expr] = choice2
            result.append(c2)
    return result