How many distinct permutations of word A contain word B? Output the remainder when this number is divided by 10007.

Input

The first line contains a sequence of lowercase English letters, word A. The length of the sequence will not exceed 500. The second line contains a sequence of lowercase English letters, word B. Word B will not be longer than word A.

Output

In the first and only line, output the remainder when the required number of permutations is divided by 10007.

Examples

Input 1

mirko
mir

Output 1

6

Note 1

The six permutations that contain the word mir are: kmiro, komir, mirko, mirok, okmir, and omirk.

Input 2

sssss
ss

Output 2

1

Input 3

barbarabarbara
barbabarba

Output 3

30