Given 2 binary strings A and B of each with length at most 175, we want to combine them to produce a new string C the following way: As long as either one of strings A, B choose one of them (as long as it's non empty) add the first character in the chosen string to the end of C and then delete from that string. The task is for each distinct possible resulting C sum the square of the number of ways you can arrive at it with that procedure modulo some prime.

This problem was presented in a local IOI selection in 2012, we suspect it was ripped from some USACO related contest (since all other problems that year were also stolen from there), so I don't really have a link for it but I know it's possible to solve it. Any ideas? Thanks in advance.