Statement

Edoardo just found a beautiful 4D rendering software. Unfortunately, this software is not free, and a valid license key must be entered to use it. Edoardo, however, reverse engineered the program and found the function that checks the key! The function takes K boolean variables, named as the first K lowercase letters of the English alphabet (i.e. "a", "b", etc…). These variables are combined in a boolean formula represented by a string S. The formula is a XOR of multiple clauses, where each clause is the AND of some literals: a variable (positive literal) or its negation (negative literal). In order to generate a valid license, Edoardo needs to find a way to assign each variable 0 or 1 such that the given formula evaluates to 1. Edoardo wants to generate as many valid licenses as possible to sell them on the dark web. Help Edoardo find the number of different licenses he can sell!