DNA Base Pair Completion

In biology, we know that bases form DNA (deoxyribonucleic acid). They are represented by the uppercase letters $A,C,T,G$, with the pairings given by $A \leftrightarrow T$ and $C \leftrightarrow G$. Two DNA sequences match if and only if they have the same length and every pair of corresponding bases are complementary.

For example, the sequence ACGTC can match with TGCAG because for every index i, the base in the first sequence and the base in the second sequence are complementary.

A shorter sequence can be completed to match a longer sequence by inserting additional bases at arbitrary positions. Different choices of insertion positions and counts yield distinct completion schemes.

You are given two base sequences, S and T, consisting of n and m bases respectively, where $n \ge m$. The task is to count the number of ways to complete the shorter sequence so that it becomes complementary to the longer sequence. The complementary sequence for S is determined by replacing each base by its pair ($A \to T$, $T \to A$, $C \to G$, $G \to C$). A valid completion is one where, after inserting extra bases into the shorter sequence (without changing the order of the existing bases), the resulting sequence exactly matches the complementary sequence of the longer sequence.

Note: If the two sequences are of equal length, then there is exactly one valid completion if every base in T is already complementary to the base at the corresponding position in S; otherwise, the answer is 0.

This problem can be approached using dynamic programming by counting the number of subsequences of the complementary sequence of the longer sequence that are equal to the given shorter sequence.

inputFormat

The input consists of two lines. The first line contains the sequence S (having n bases). The second line contains the sequence T (having m bases, where $n \ge m$).

outputFormat

Output a single integer which is the number of distinct ways to complete the shorter sequence to make it complementary to the longer sequence.

sample

ACGTC
TGCAG

1