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)