Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- #define ull unsigned long long
- #define ll long long
- #define MM 1000000007
- #define N 100005
- #define pb push_back
- #define p_q priority_queue
- #define pii pair<ll,ll>
- #define vi vector<ll>
- #define vii vector<pii>
- #define mi map<ll,ll>
- #define mii map<pii,ll>
- #define all(a) (a).begin(),(a).end()
- #define sz(x) (ll)x.size()
- #define endl '\n'
- #define Endl '\n'
- #define gcd(a,b) __gcd((a),(b))
- #define lcm(a,b) ((a)*(b)) / gcd((a),(b))
- #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define mp make_pair
- #define lb lower_bound
- #define ub upper_bound
- #define F first
- #define S second
- #define rep(i, begin, end) for(int i=begin;i<end;i++)
- #define repr(i,begin,end) for(int i=end-1;i>=begin;i--)
- #define ini(a,n,b) for(ll int i=0;i<n;i++) a[i]=0;
- #define cset(a) __builtin_popcountll(a)
- #define hell (ull)1e9
- #define re resize
- int dp[1000][1000],n;
- vector<int> inde[26];
- string t;
- int fun(int ind,int prev)
- {
- if(ind==sz(t)) return 1;
- if(dp[ind][prev]!=-1) return dp[ind][prev];
- int c=t[ind]-'a';
- int ans=0;
- for(int i:inde[c])
- {
- if(i>prev)
- {
- ans=(ans+fun(ind+1,i))%MM;
- }
- }
- return dp[ind][prev]=ans;
- }
- signed main(void)
- {ios
- int TESTS=1;
- //cin>>TESTS;
- while(TESTS--)
- {
- cin>>n;
- rep(i,0,n)
- {
- string s;
- cin>>s;
- for(int j=0;j<s.size();j++) inde[s[j]-'a'].pb(j);
- }
- cin>>t;
- memset(dp,-1,sizeof(dp));
- int ans=0;
- int c=t[0]-'a';
- for(int i:inde[c])
- {
- ans=(ans+fun(1,i))%MM;
- }
- cout<<ans;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement