1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 #include using namespace std; using lld = long long; const int MAXN = 1e4+1; const lld mod = 1e9+7; lld bin[MAXN+5][MAXN+5]; lld f(lld a, lld b){ return (bin[a+1][b+1]-bin[a+1][b]+mod) % mod; } lld field1(int r, string& s){ return bin[s.length()+1][r+1]; } lld field2(int r1, string& s1, int r2, string& s2){ lld res = 0; int a=0,b=0; for(int i=0;i= 0) res = (res + (f(a,p) * bin[b+1][M+1]) % mod) % mod; } return res; } lld field3(int r1, string& s1, int r2, string& s2, int r3, string& s3){ int x,y,z,t; x = y = z = t = 0; lld res = 0; for(int i=0;i= 0) res += (m3 * bin[x+1][M+1]) % mod; } } } return res; } void solve2(int r1, string& s1, int r2, string& s2){ cout << (field1(r1,s1) + field1(r2,s2) + mod-field2(r1,s1, r2,s2)) % mod << "\n"; } void solve3(int r1, string& s1, int r2, string& s2, int r3, string& s3){ lld res = 0; res += field1(r1,s1); res += field1(r2,s2); res += field1(r3,s3); res += mod-field2(r1,s1, r2,s2); res += mod-field2(r2,s2, r3,s3); res += mod-field2(r3,s3, r1,s1); res += field3(r1,s1, r2,s2, r3,s3); cout << res%mod << "\n"; } int main(void){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; bin[1][1] = 1; for(int i=2;i<=MAXN;i++) for(int j=1;j<=i;j++) bin[i][j] = (bin[i-1][j-1] + bin[i-1][j]) % mod; for(int i=1;i<=MAXN;i++) for(int j=1;j<=i;j++) bin[i][j] = (bin[i][j] + bin[i][j-1]) % mod; int r1,r2,r3; string s1,s2,s3; cin >> r1 >> s1 >> r2 >> s2 >> r3 >> s3; if(r1 == r2 && s1 == s2) solve2(r1,s1, r3,s3); else if(r1 == r3 && s1 == s3) solve2(r1,s1, r2,s2); else if(r2 == r3 && s2 == s3) solve2(r1,s1, r3,s3); else solve3(r1,s1, r2,s2, r3,s3); return 0; }