Acronym Expansion Count

In this problem, you are given an abbreviation and a corresponding full name composed of several words (separated by single spaces). Note that the full name may include irrelevant words that should be ignored.

An explanation (expansion) of the abbreviation is defined as follows: You choose some of the words (in their original order), and from each chosen word you pick a non‐empty subsequence of characters (i.e. characters picked in order from the word) so that when concatenated, they form the abbreviation exactly. Every chosen word (i.e. every word used in the explanation) must contribute at least one letter. Two explanations are considered different if there is at least one chosen letter which comes from a different character position in its word.

Formal description:

Let \(S\) be the abbreviation (of length \(m\)) and the full name consists of words \(W_1, W_2, \dots, W_n\). You are allowed to skip any word. For any word that you use, you select a non-empty subsequence of its letters that exactly matches a contiguous segment of \(S\) (with the segments taken in order to form \(S\)). Count the number of ways to form \(S\) under these conditions.

Note: All comparisons are case-sensitive and the letters in the chosen subsequences must appear in the same order as in the word.

The answer may be large; however, you can assume that the final result fits in a standard 64-bit integer.

inputFormat

The input consists of two lines. The first line contains the abbreviation \(S\) (a non-empty string of uppercase letters). The second line contains the full name, which is a sequence of one or more words separated by single spaces. Each word is a non-empty string of letters.

outputFormat

Output a single integer, representing the number of valid explanations for the abbreviation.

sample

ABC
ALPHA BETA GAMMA

0