Cho 2 xâu s1 và s2. Ta có thể trộn các kí tự của hai xâu (theo thứ tự ban đầu) để được xâu mới.

Ví dụ: s1 = 'ab' và s2 = 'ba'.

Ta có thể trộn để được xâu st = 'a b b a' nhưng không được st = 'a a b b'.

Yêu cầu: Cho 2 xâu chỉ gồm các chữ cái thường. Đếm số cách trộn để tạo được xâu palindrome.

Ví dụ: aba, abba là palindrome, abc và abca không phải.

Input

2 dòng, mỗi dòng chứa một xâu, độ dài xâu không vượt quá ~500~.

Output

Một số nguyên là số cách trộn sau khi ~\bmod 3210121~.

Sample Input

ab
ba

Sample Output

4