You are given a multiset of lowercase letters (as a string s, possibly with repeated letters) and two distinct lowercase letters x and y that are known to "clash". Count the number of DISTINCT arrangements (as strings) of all the letters in s — treating repeated letters as indistinguishable, so arrangements that look identical as strings are counted once — such that x and y never appear directly next to each other anywhere in the arrangement.

If x or y does not occur in s at all, the adjacency condition can never be violated, so every distinct arrangement of s counts.

Input format

Line 1: the string s. Line 2: two distinct lowercase letters x and y, space-separated.

Output format

A single integer: the number of distinct arrangements of s in which x and y are never adjacent.

Constraints

• 1 ≤ length of s ≤ 8
• s contains only lowercase English letters
• x and y are distinct single lowercase letters (they may or may not appear in s)

aabc
b c

6

ab
a b

0