#line 87 "ColorfulGardenHard.cpp"
#include <iostream>
#include <string>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <map>
#include<unordered_map>
#include <set>
#include <cstring>
#include <iomanip>
#include <list>
#include <bitset>
//#include<bits/stdc++.h>
#define itn int
#define mp make_pair
#define endl "\n"
using namespace std;
typedef long long ll;
int mod = 1e9 + 7 ;
ll powmod(ll a,ll b) {ll res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
ll gcd(ll a , ll b){return b==0?a:gcd(b,a%b); }
string s1,s2;
ll dp[100010][30],n;

ll func(ll mask,ll cur)
{
    ll bits=(ll)__builtin_popcount(mask);
    if(bits==n) return 1;
    if(dp[mask][cur]!=-1)
        return dp[mask][cur];
    ll temp[30];
    
    memset(temp,0,sizeof(temp));
    ll i,j;
    for(j=0;j<n;j++)
    {
        if(mask&(1<<j))
            continue;
        else temp[s1[j]-'a']++;
    }
    
    ll tempans=0;
    for(i=0;i<26;i++)
    {
        if(temp[i]>0 && i!=cur && s2[bits]-'a'!=i)
        {
            //aacout<<"i="<<i<<endl;
            for(j=0;j<n;j++)
            {
                if(mask&(1<<j))
                {
                    //cout<<"j in mask="<<j<<endl;
                    continue;
                }
                else
                {
                    
                    if(s1[j]-'a'==i)
                    {
                        //cout<<"i="<<i<<endl;
                        tempans=(tempans+func(mask|(1<<j),i))%mod;
                        break;
                    }
                }
            }
        }
    }
    return dp[mask][cur]=tempans;
}

class ColorfulGardenHard {
	public:
	int count(string garden, string forbid) {
        s1=garden; s2=forbid;
        ll i,j,m,ans=0;
        memset(dp,-1,sizeof(dp));
        ll temp[27];
        memset(temp,0,sizeof(temp));
        for(i=0;i<s1.length();i++)
        {
            temp[s1[i]-'a']++;
        }
        n=s1.length();
        for(i=0;i<26;i++)
        {
            if(temp[i]>0)
            {
                for(j=0;j<n;j++)
                {
                    if(s1[j]-'a'==i && s2[0]-'a'!=i)
                    {
                        //cout<<"i="<<i<<endl;
                        ans=(ans+func(1<<j,i))%mod;
                        //cout<<endl<<endl<<endl;
                        break;
                    }
                    
                }
            }
        }
        return ans;

	}
};















// Powered by FileEdit