TPCPALIN - Palindrome Merge

no tags 

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/tpcpalin


Cho 2 xâu s1 và s2. Ta có thể trộn các kí tự của 2 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 = 'abba' nhưng không được st = 'aabb'.

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 mod 3210121.

Example

Input:
ab
ba

Output:
4



Added by:Mew.
Date:2014-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64