Logic Gate Pipeline

You are designing a processor pipeline using N unique logic gates. Each gate has a specific input signal type and output signal type (represented by single characters). To form a valid pipeline, you must use ALL N gates exactly once in some order. The first gate's input must match a required Start type, and the last gate's output must match a required End type. For any two adjacent gates in the sequence, the output type of the first must match the input type of the second. Calculate how many valid permutations of all N gates exist. Input: First line: Start type and End type (chars). Second line: N (integer). Next N lines: Two space-separated characters representing the input and output type of each gate. Output: Total count of valid pipelines. Example: Input: A C 2 A B B C Output: 1