Permutations that contain a word

Count distinct permutations of A that contain B as a contiguous substring, modulo 10007.

Hard8Dynamic programmingCombinatoricsString matchingMathNo attempts yetTime limit2sMemory limit128 MB

Description

Examples3

Problem

You are given two words $A$ and $B$ , both written with lowercase English letters. Rearranging all the letters of $A$ produces many words. Count the distinct words obtained this way that contain $B$ as a contiguous substring. Two rearrangements that produce the same word count once.

Compute the remainder of that count divided by $10007$ .

Input

The first line contains the word $A$ , written with lowercase English letters. The length of $A$ is at most $500$ .

The second line contains the word $B$ , written with lowercase English letters. The word $B$ is not longer than the word $A$ .

Output

Print the remainder of the number of such words divided by $10007$ on the first line.

Note

If $A$ is mirko and $B$ is mir, the six words are kmiro, komir, mirko, mirok, okmir, omirk.