Vasya started to use the Internet not so long ago, so he has
only two e-mail accounts at two different servers. For each of them he has a password, which is a
non-empty string consisting of only lowercase latin letters. Both mail servers accept a string as a password if and only if the real password is its subsequence.

Vasya has a hard time memorizing both passwords, so he would like to come up
with a single universal password, which both servers would accept. Vasya can't
remember too long passwords, hence he is interested in a universal password
of a minimal length. You are to help Vasya to find the number of such passwords.

### Input

The input consists of 2 lines, each of them containing the real password for one of the servers.
The length of each password doesn't exceed 2000 characters.

### Output

Output the number of universal passwords of minimal length modulo 10^{9} + 7.

### Samples

input | output |
---|

b
ab
| 1 |

abcab
cba
| 4 |

### Notes

In the second sample, the passwords of minimal length are the following: **abcaba, abcbab, acbcab, cabcab**.

**Problem Author: **Igor Chevdar

**Problem Source: **USU Junior Contest, October 2007