Ways of forming palindromic strings

Question

The following problem was given to us in the recruitment test of InMobi.
Given a list of strings $\{a_1, a_2,..,a_n\}$, I want to count the number of ways of forming PALINDROMIC string $S=s_1+s_2+..+s_n$, where $s_i$ represents a non-empty sub-sequence of string $a_i$.
As answer can be large to fit in integer bounds, give ans mod $10^9+7$
Example: Given strings $\{zz, a, zz\}$, there are $5$ ways of forming $S$.
$zaz$ can be formed in $4$ ways and $zzazz$ in $1$ way.

Answer 1

Concatenate all strings and find the number of palindromic subsequences. Now you have to remove those ways in which theres atleast one string that did not participate in palindrome formation. So make all $2^n$ combinations of strings that didn't participate and calculate the number of palindromic subsequences formed by rest of them and keep on subtracting this from answer.
Finding palindromic subsequences in a string is a simple $O(n^2)$ dp. So overall complexity would be $O(2^n.n^2)$