【问题描述】

求三个字符序列的公共子序列个数。

【输入数据】

第一行为一个正整数N，表示3个序列的长度。 　　 接下来3行，每行一个无空格长度为N的字符序列。只包含小写字母a到z。

【输出数据】

一行一个正整数ANS。ANS可能较大，输出对100000000取模的结果。

【样例输入】

4
aabb
abab
baba

【样例输出】

5

【数据规模】

对于30％的数据，N≤10；

对于70％的数据，N≤50；

对于100％的数据，N≤150。

【注意事项】

5种子序列是a，ab，aa，bb，b。