TPCPALIN - Palindrome Merge

no tags 

 

Given two strings s1 and s2. We can merge characters of two strings (with order in original strings) to get a new string.

For example : s1 = 'ab' and s2 = 'ba'.

We can merge to get st = 'abba' but not st = 'aabb'.

The Problem : Given two string contain only lowercase letters, count the number of palindrome by merging in different ways. 

Ex : 'aba', 'abba' are palindrome, 'abc' and 'abca' aren't.

Input

- Two lines, each line contains a string, string's length isn't over 500.

Output

- A single integer is the number of palindrome after modul 3210121.

Example

Input:
ab
ba

Output:
4


hide comments
D Pratap : 2014-09-30 19:54:19

In the given example from two strings
ab
ba

only two palindromes can be obtained


abba

baab


how the answer is 4

RE (Jacob): We want the number of different ways of merging the strings to yield a palindrome (where a "way" is a certain sequence of which of the 2 strings each letter comes from), not the number of distinct palindromes.

Last edit: 2014-09-30 06:46:13
Mew.: 2014-09-30 19:54:19

No, keep order in original string.

ivar.raknahs: 2014-09-30 19:54:19

@Mew:can the string be reversed and then merged?


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