Given two strings $S$ and $T$.

Let $S_{l,r}$ denote the substring of $S$ from the $l$-th to the $r$-th character.

A substring of $S_{l,r}$ is defined as any $S_{x,y}$ such that $l \leq x \leq y \leq r$.

Let $f(l,r)$ be the sum of the number of occurrences of all substrings of $S_{l,r}$ in $T$.

You need to calculate:

$$\sum_{i=1}^{|S|} \sum_{j=i}^{|S|} f(i,j) \cdot(j-i+1)^2$$

modulo $(10^9+7)$.

Input

Read the data from standard input.

The input consists of two lines, each containing a string consisting only of lowercase letters, representing $S$ and $T$ respectively.

Output

Output to standard output.

Output a single integer representing the result of the expression in the problem description modulo $(10^9+7)$.

Examples

Input 1

aba
ba

Output 1

59

Input 2

ababc
babac

Output 2

1094

Input 3

aaaaa
aa

Output 3

1008

Input 4

arknights
genshinimpact

Output 4

5901

Subtasks

Let $\max(|S|,|T|)=n$.

• Subtask 1 (10 points): $1 \leq n \leq 60$.
• Subtask 2 (20 points): $1 \leq n \leq 300$.
• Subtask 3 (30 points): $1 \leq n \leq 2\,000$.
• Subtask 4 (25 points): $1 \leq n \leq 20\,000$.
• Subtask 5 (15 points): $1 \leq n \leq 500\,000$.