As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has n 01 strings si, and he wants to know the number of 01 antisymmetric strings of length 2L which contain all given strings si as continuous substrings.
A 01 string s is antisymmetric if and only if s[i]≠s[|s|−i+1] for all i∈[1,|s|].
It is too difficult for Rikka. Can you help her?
In the second sample, the strings which satisfy all the restrictions are 000111,001011,011001,100110.
Yuta has n 01 strings si, and he wants to know the number of 01 antisymmetric strings of length 2L which contain all given strings si as continuous substrings.
A 01 string s is antisymmetric if and only if s[i]≠s[|s|−i+1] for all i∈[1,|s|].
It is too difficult for Rikka. Can you help her?
In the second sample, the strings which satisfy all the restrictions are 000111,001011,011001,100110.
