Problem:


Score : 500 points

Problem Statement

You are given two integer sequences S and T of length N and M, respectively, both consisting of integers between 1 and 10^5 (inclusive).

In how many pairs of a subsequence of S and a subsequence of T do the two subsequences are the same in content?

Here the subsequence of A is a sequence obtained by removing zero or more elements from A and concatenating the remaining elements without changing the order.

For both S and T, we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.

Since the answer can be tremendous, print the number modulo 10^9+7.

Constraints

1 \leq N, M \leq 2 \times 10^3

The length of S is N.

The length of T is M.     

1 \leq S_i, T_i \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
S_1 S_2 ... S_{N-1} S_{N}
T_1 T_2 ... T_{M-1} T_{M}

Output

Print the number of pairs of a subsequence of S and a subsequence of T such that the subsequences are the same in content, modulo 10^9+7.

Sample Input 1

2 2
1 3
3 1

Sample Output 1

3

S has four subsequences: (), (1), (3), (1, 3).

T has four subsequences: (), (3), (1), (3, 1).

There are 1 \times 1 pair of subsequences in which the subsequences are both (), 1 \times 1 pair of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (3), for a total of three pairs.

Sample Input 2

2 2
1 1
1 1

Sample Output 2

6

S has four subsequences: (), (1), (1), (1, 1).

T has four subsequences: (), (1), (1), (1, 1).

There are 1 \times 1 pair of subsequences in which the subsequences are both (), 2 \times 2 pairs of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (1,1), for a total of six pairs.
Note again that we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.

Sample Input 3

4 4
3 4 5 6
3 4 5 6

Sample Output 3

16

Sample Input 4

10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7

Sample Output 4

191

Sample Input 5

20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

846527861

Be sure to print the number modulo 10^9+7.



Sample input:
2 2
1 3
3 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    S = LI()
    T = LI()

    dp = [[1]*(M+1) for _ in range(N+1)]

    for i in range(1,N+1):
        for j in range(1,M+1):
            dp[i][j] =dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

            if S[i-1] == T[j-1]:
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
 
M = 10**9+7
 
dp = [[0]*(m+1) for _ in range(n+1)]
dp[0][0] = 1
 
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
    else:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
    dp[i+1][j+1] %= M
 
#print(dp)
print(dp[-1][-1]%M)

Submission status: Wrong Answer

Solution code:
from numpy import*
N,M,*U= map(int,open(0).read().split())
T=array(U[N:])
p=ones(M+1)
for s in U[:N]:p[1:]=((p[:-1]*(s==T)).cumsum()+p[1:])%(10**9+7)
print(p[-1])

Submission status: Wrong Answer

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
S = LI()
T = LI()

MOD = 10 ** 9 + 7


def main():
    S.reverse()
    T.reverse()
    w = [0] * (M + 1)
    for s in S:
        l = [0] * (M + 1)
        x = 0
        for i in range(M):
            l[i + 1] = w[i + 1] + x
            if T[i] == s:
                x = (x + w[i] + 1) % MOD
                l[i + 1] = (l[i + 1] + w[i] + 1) % MOD
        w = l
    
    ans = w[-1] + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
s,t = map(int, raw_input().split(' ')), map(int, raw_input().split(' '))
dp,prefix = [[0 for j in range(len(t))] for i in range(len(s))], [[0 for j in range(len(t))] for i in range(len(s))]
total = 1
mod = (10 ** 9) + 7
for ii in range(len(s)):
	for jj in range(len(t)):
		if s[ii] == t[jj]:
			dp[ii][jj] = 1+ prefix[ii-1][jj-1] if ii-1>=0 and jj-1>=0 else 0
			total += dp[ii][jj] % (mod)
		prefix[ii][jj] += prefix[ii - 1][jj] if ii - 1 >=0 else 0
		prefix[ii][jj] += prefix[ii][jj - 1] if jj - 1 >=0 else 0
		prefix[ii][jj] -= prefix[ii - 1][jj - 1] if (jj - 1 >=0) and (ii-1) >=0 else 0
		prefix[ii][jj] += dp[ii][jj]
			
print total

Submission status: Wrong Answer

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
s,t = map(int, raw_input().split(' ')), map(int, raw_input().split(' '))
dp,prefix = [[0 for j in range(len(t))] for i in range(len(s))], [[0 for j in range(len(t))] for i in range(len(s))]
total = 1
for ii in range(len(s)):
	for jj in range(len(t)):
		if s[ii] == t[jj]:
			dp[ii][jj] = 1+ prefix[ii-1][jj-1] if ii-1>=0 and jj-1>=0 else 0
			total += dp[ii][jj]
		prefix[ii][jj] += prefix[ii - 1][jj] if ii - 1 >=0 else 0
		prefix[ii][jj] += prefix[ii][jj - 1] if jj - 1 >=0 else 0
		prefix[ii][jj] -= prefix[ii - 1][jj - 1] if (jj - 1 >=0) and (ii-1) >=0 else 0
		prefix[ii][jj] += dp[ii][jj]
			
print total

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[(m+1)*[1]for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
    if s[i]!=t[j]:dp[i+1][j+1]-=dp[i][j]
    dp[i+1][j+1]%(10**9+7)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
#N,M = map(int,input().split())
#S = list(map(int,input().split()))
#T = list(map(int,input().split()))
mod = 10**9+7
N,M = 1989,1915
S = list(map(int,"19 122 69 99 57 161 75 161 144 111 102 68 119 85 196 71 121 132 27 135 18 152 108 37 26 183 139 126 127 195 143 51 161 54 194 84 147 152 55 105 57 99 86 100 156 32 12 147 186 196 148 98 100 162 131 39 9 137 1 67 81 56 30 175 133 164 64 180 174 143 98 38 193 75 176 88 193 43 181 50 189 15 55 107 97 54 113 70 125 125 161 106 100 163 29 15 72 159 15 62 167 2 122 89 88 168 200 14 35 3 181 6 126 81 13 90 117 153 160 82 106 84 131 176 26 164 74 141 33 193 29 199 89 85 134 56 62 164 100 85 65 167 95 128 149 200 109 53 18 31 137 3 37 137 124 171 91 47 173 86 42 171 190 163 198 50 75 182 67 61 148 130 35 129 141 137 1 58 85 91 19 140 85 168 136 48 52 173 106 8 100 47 82 3 117 88 128 94 116 89 168 24 54 151 144 139 45 140 116 40 16 18 116 15 168 184 33 160 183 46 187 4 145 112 59 198 183 38 16 51 19 3 104 55 131 150 95 181 5 126 94 163 39 10 41 87 169 165 133 4 159 109 193 161 28 41 20 169 101 198 155 10 148 164 55 181 95 197 158 48 11 123 58 110 31 197 109 145 157 190 124 84 61 111 50 160 189 17 39 55 149 6 85 134 146 88 45 99 154 60 44 103 39 190 121 126 193 155 194 77 152 166 167 41 107 88 193 180 156 42 2 59 131 152 165 139 133 75 138 84 31 82 95 155 139 113 135 32 10 119 117 61 100 66 40 24 150 108 193 6 144 75 45 190 122 46 114 143 85 27 158 156 12 91 104 54 141 6 60 27 5 147 161 140 190 12 163 62 2 94 176 37 172 55 126 84 33 142 147 21 185 169 22 170 53 136 56 180 169 28 195 135 195 150 169 37 42 4 195 138 110 20 163 135 44 182 46 22 68 186 198 113 16 126 150 1 130 79 160 102 46 20 193 73 109 173 32 10 101 82 188 187 144 70 70 8 162 22 200 102 106 114 104 1 11 107 76 64 68 138 99 186 193 67 194 77 103 3 141 115 154 124 73 73 163 93 130 74 179 192 189 191 155 126 22 122 90 39 78 180 200 195 140 153 101 144 150 25 153 128 161 26 45 170 96 173 129 16 71 194 53 67 128 155 39 144 15 87 155 200 127 159 180 16 23 197 160 180 87 130 122 19 198 157 6 114 120 93 150 80 91 143 165 68 49 95 178 44 26 99 130 70 174 166 67 165 142 91 131 86 110 100 179 115 39 162 75 86 47 103 99 49 54 159 108 83 183 112 83 52 31 7 48 193 198 153 124 169 30 79 140 53 49 49 85 167 132 198 25 148 178 22 191 34 157 119 85 7 6 43 18 65 117 67 2 28 150 150 177 38 51 144 183 68 70 125 200 158 115 127 188 134 125 106 198 116 47 167 15 61 62 45 59 59 17 86 91 45 32 162 162 20 136 43 159 126 182 32 178 119 123 29 112 112 7 40 139 11 97 146 160 55 23 44 175 130 168 36 184 68 80 90 193 191 185 77 158 117 74 136 30 58 119 54 134 127 111 59 29 118 197 125 60 160 68 88 157 191 17 129 79 68 116 121 178 60 142 36 100 128 66 116 7 38 182 13 95 190 101 106 71 150 154 92 185 56 90 82 195 104 7 86 150 47 137 117 60 137 10 39 110 33 55 48 100 65 99 109 66 139 31 23 62 49 125 164 71 134 184 174 81 19 84 42 132 190 10 102 152 102 125 134 176 143 89 6 148 16 12 52 79 135 116 60 46 195 149 155 48 54 156 182 18 15 159 100 89 28 22 131 152 78 15 67 144 156 144 97 146 185 130 186 122 131 108 169 40 16 42 27 82 184 3 101 81 185 41 185 166 23 2 187 114 189 48 9 184 136 15 57 174 24 70 45 20 144 96 150 91 105 83 169 101 39 26 85 61 88 53 190 133 100 29 69 46 130 75 24 130 98 120 127 23 176 2 103 5 162 52 79 84 128 62 129 123 136 53 66 3 178 63 85 174 37 108 188 34 179 162 54 5 173 156 194 189 36 85 193 181 134 86 39 28 177 199 113 78 159 56 63 9 13 188 138 138 155 176 93 35 148 45 88 159 69 30 66 153 117 184 30 134 178 92 177 138 186 174 107 38 6 93 166 66 14 59 73 114 141 10 27 153 96 135 184 110 131 93 106 16 198 127 67 7 12 165 139 23 190 69 53 198 173 66 120 45 183 169 81 96 184 75 157 74 94 142 6 174 81 115 80 145 72 172 41 64 58 43 125 86 184 56 125 28 116 183 177 79 31 102 113 60 112 40 139 153 42 61 53 60 112 128 64 15 5 72 129 2 76 184 113 59 121 23 165 142 50 7 60 179 127 147 68 21 95 149 61 59 72 6 97 144 126 102 79 190 89 150 184 8 18 198 98 43 183 112 1 149 65 7 100 153 21 97 35 75 72 152 125 101 176 7 30 80 52 179 177 38 84 179 79 34 128 129 8 27 59 64 77 172 198 16 108 58 54 20 120 18 90 23 188 87 33 57 196 85 188 131 123 19 4 127 166 83 108 165 178 61 15 22 89 143 142 175 52 138 198 1 143 98 181 61 89 123 1 182 30 148 152 133 181 113 164 83 75 108 91 74 172 57 139 130 60 66 148 91 60 16 188 10 1 153 36 181 100 22 46 192 160 120 9 122 126 2 9 166 124 113 127 132 170 12 50 78 164 143 193 175 99 6 11 187 11 59 145 149 17 167 12 72 125 106 192 169 64 4 157 16 5 132 139 26 181 50 135 23 152 12 153 149 71 158 179 75 19 22 139 162 45 93 14 132 36 18 110 23 191 171 48 184 123 106 96 139 73 132 28 58 196 92 66 35 195 131 56 77 133 66 68 162 145 138 32 57 170 62 18 197 179 199 103 89 40 19 56 158 131 164 18 58 95 101 79 194 168 160 56 37 145 49 77 167 54 59 14 50 31 117 133 123 148 198 74 171 175 7 138 51 119 123 135 115 131 128 113 18 138 100 32 9 131 171 3 98 17 183 193 97 104 31 147 167 33 40 167 60 9 171 24 30 79 3 133 50 128 49 137 114 89 64 32 22 67 192 157 115 127 135 139 183 116 68 52 98 193 65 17 66 5 54 42 23 2 107 171 37 18 56 97 200 77 100 122 147 51 98 186 151 51 198 83 54 22 199 168 141 106 183 128 144 188 138 196 42 143 155 155 14 15 161 80 190 169 10 184 20 44 5 106 93 8 26 155 129 33 107 26 99 174 72 6 153 183 181 47 148 1 34 153 126 165 92 94 137 3 54 192 126 39 89 136 177 26 184 94 142 182 68 93 27 88 12 27 23 78 131 135 102 135 40 117 141 32 36 135 72 119 144 146 123 142 126 122 70 146 173 53 185 157 190 63 95 178 55 109 161 119 100 78 132 168 105 35 52 48 123 60 31 123 122 113 150 36 78 138 77 17 56 101 2 133 17 168 126 96 39 36 58 108 200 47 193 73 37 32 179 169 68 159 71 158 200 26 139 127 104 8 172 34 77 113 110 196 153 116 100 196 71 181 52 26 98 179 187 93 79 5 48 1 41 81 9 41 16 137 71 119 98 41 90 34 1 34 159 24 80 89 105 20 106 50 161 124 160 167 121 123 49 139 156 143 25 63 107 118 198 30 51 11 106 164 102 141 119 147 46 150 138 114 113 135 80 124 117 109 101 115 96 117 136 84 9 54 66 119 1 78 178 17 78 173 23 198 27 107 48 196 46 191 200 180 112 12 187 35 18 107 135 42 173 25 77 21 155 77 134 61 35 35 18 194 193 117 174 150 52 48 110 61 129 35 172 71 104 26 117 42 51 28 5 144 165 75 97 8 98 84 145 153 173 95 27 27 129 134 57 177 185 186 141 125 2 195 176 45 44 85 162 106 124 154 165 75 181 109 147 13 38 120 17 177 188 120 108 129 77 193 171 169 54 132 3 24 92 150 128 38 5 129 19 54 168 104 108 158 171 68 183 141 92 53 94 45 32 22 102 140 153 126 73 125 48 155 181 163 118 108 185 186 99 169 4 97 189 177 177 10 41 177 187 160 18 75 131 90 175 28 125 4 9 129 172 18 19 38 68 94 57 154 139 33 43 2 9 167 65 68 143 33 136 104 186 192 9 31 2 68 89 186 144 168 79 127 138 107 189 198 93 78 61 85 47 61 65 125 82 169 108 38 110 6 167 190 110 90 121 54 155 158 59 132 2 136 62 30 84 17 125 16 179 4 90 36 136 72 54 141 199 171 99 46 185 3 152 25 145 10 130 166 41 151 94 184 179 22 8 110 137 118 39 147 109 87 141 143 167 37 176 183 43 197 22 86 77 104 183 87 185 15 123 47 58 163 83 11 106 143 35 46 47 75 64 118 44 7 29 144 143 164 125 143 147 42 152 32 180 99 142 117 181 3 54 164 53 67 125 162 85 178 147".split()))
T = list(map(int,"41 127 128 64 3 167 81 96 42 103 51 79 151 6 109 46 29 60 107 125 67 173 72 79 3 119 17 77 10 129 131 146 2 199 35 166 53 138 11 188 29 157 63 186 200 3 67 82 3 80 48 19 17 130 126 97 15 71 197 193 79 31 150 183 133 148 25 28 79 77 140 42 10 165 132 72 9 16 175 123 200 131 57 20 169 92 18 192 137 190 43 21 61 165 107 53 33 127 124 40 163 143 165 195 176 121 4 151 110 29 18 151 92 121 12 180 2 102 38 159 180 132 12 1 62 149 49 79 14 121 142 12 166 70 92 38 156 19 106 167 72 186 51 118 198 162 161 6 69 61 101 129 195 68 31 151 74 44 30 37 67 7 78 93 61 82 157 41 30 30 37 14 101 179 147 164 79 119 59 62 34 56 108 6 65 115 187 67 80 82 131 99 73 135 130 88 163 185 9 106 198 194 8 188 135 84 80 166 26 167 111 8 149 117 53 72 162 119 99 107 133 75 119 39 40 132 175 121 46 35 126 72 36 20 37 87 187 161 197 42 99 123 72 99 54 196 44 72 167 131 200 194 185 79 188 49 34 126 115 35 92 99 94 54 159 196 23 135 105 177 196 65 18 153 74 149 58 74 112 92 1 3 6 143 92 137 31 65 106 119 190 61 71 94 100 168 99 128 150 127 185 111 120 131 77 196 142 118 95 192 134 19 38 140 154 54 191 185 178 26 196 163 141 168 71 168 105 196 61 155 68 134 68 173 113 157 142 117 195 186 47 71 5 10 89 39 48 145 188 109 191 10 13 61 111 92 185 10 20 48 108 78 109 198 84 132 153 2 127 80 160 80 30 172 91 56 15 142 166 93 95 112 22 148 189 200 139 4 154 97 176 119 125 141 139 42 122 143 76 76 37 36 173 75 95 28 164 100 77 46 166 85 160 196 19 79 15 60 194 6 149 69 149 146 132 150 38 188 138 112 17 133 52 53 58 80 122 66 73 6 178 191 106 119 125 178 108 165 60 179 143 100 159 7 86 93 180 61 67 38 57 124 114 162 101 41 58 144 40 118 146 39 48 59 143 93 11 107 45 9 176 160 114 71 82 186 110 30 25 48 38 80 184 76 78 10 21 175 43 89 11 41 152 58 173 145 168 190 17 117 50 149 33 145 91 116 57 124 59 172 139 54 5 114 56 31 88 68 85 182 21 116 81 134 53 95 55 85 154 50 79 48 195 199 136 62 190 89 71 193 169 55 34 183 123 33 154 113 95 98 27 177 69 108 51 123 26 154 171 13 126 145 186 133 71 68 171 167 48 44 58 68 153 118 93 34 18 151 67 144 187 129 43 6 164 1 54 160 57 51 67 175 110 4 95 35 30 4 152 123 147 102 26 97 193 63 55 155 6 111 31 61 77 114 43 166 14 153 171 146 31 176 174 47 4 185 73 155 186 6 81 190 37 5 133 157 38 170 71 15 21 189 93 126 56 195 197 171 127 197 106 164 39 186 168 199 172 42 9 43 150 153 79 113 149 86 190 19 98 15 38 188 43 193 155 42 71 6 147 184 157 174 191 199 144 45 67 48 177 131 171 145 188 9 101 35 147 1 162 133 35 156 195 132 97 78 158 39 161 98 72 101 126 97 26 105 44 52 133 14 99 1 74 87 11 166 116 198 25 144 15 133 163 136 109 179 24 103 94 139 67 132 25 186 17 169 56 26 126 76 81 147 78 50 102 131 158 38 121 172 83 108 80 50 16 173 48 70 75 127 77 164 143 85 95 27 60 105 120 76 188 137 108 109 101 136 8 90 94 168 28 199 100 127 130 177 55 5 133 125 42 28 103 51 197 15 158 13 181 127 189 19 77 30 168 28 161 133 172 146 120 125 135 59 81 166 197 86 114 58 22 80 1 172 187 159 36 12 108 34 156 96 29 129 144 51 20 111 51 47 64 31 139 115 119 121 181 28 48 135 85 8 96 39 133 23 8 133 156 48 26 120 82 196 137 10 53 93 55 26 8 118 42 22 93 134 18 92 65 124 62 155 187 193 50 97 51 89 82 177 169 18 181 121 92 32 35 64 101 155 159 76 157 185 200 152 160 26 139 121 97 35 146 100 74 91 16 133 64 192 48 47 83 27 138 108 132 142 104 190 115 150 59 112 32 71 11 131 106 27 3 189 84 168 190 183 30 23 135 75 81 181 151 177 34 8 26 72 178 21 54 152 196 48 191 81 20 197 95 98 156 41 185 82 190 57 115 199 125 148 104 186 73 82 184 173 47 98 44 135 73 18 45 112 2 18 38 167 173 162 158 116 65 63 180 43 63 32 55 185 92 23 86 57 37 74 143 41 95 163 128 37 187 95 60 17 54 117 14 49 7 175 146 54 55 163 175 129 4 152 139 142 175 53 166 150 107 35 66 101 83 76 29 108 121 76 173 146 148 198 143 142 36 158 12 74 111 191 78 3 20 70 52 168 119 81 100 138 96 176 91 34 162 134 106 111 43 52 146 18 85 112 22 174 67 180 197 178 71 82 137 165 191 130 167 91 68 85 178 31 142 35 106 31 185 115 128 45 112 7 136 74 162 71 198 168 42 156 199 107 117 29 105 124 190 48 140 190 147 90 197 106 130 157 142 164 132 188 99 12 116 104 14 165 153 100 135 125 137 149 159 108 183 180 179 153 22 125 16 124 12 183 13 82 115 42 78 175 54 66 128 31 18 74 62 58 152 42 105 131 15 69 45 159 65 113 75 23 133 128 124 198 55 66 44 131 64 109 83 115 12 93 140 22 50 172 127 161 43 85 32 182 5 55 70 23 69 181 34 37 182 49 15 113 167 116 47 53 138 111 188 195 85 187 32 67 113 153 62 64 119 151 44 34 32 175 92 29 16 49 126 168 137 83 14 177 84 27 42 186 111 139 69 18 146 47 32 153 95 83 130 6 116 16 132 151 157 74 80 41 195 141 140 14 191 163 188 39 30 124 124 25 178 59 64 47 115 190 10 170 125 152 96 29 104 152 63 132 29 189 152 74 53 27 43 118 190 34 146 66 185 113 45 159 96 81 156 77 121 81 140 46 94 94 81 92 96 63 12 162 18 66 68 104 55 76 63 50 198 23 64 117 190 106 135 58 17 44 65 196 51 96 47 45 85 94 154 84 169 114 2 33 185 52 158 63 34 44 21 138 181 90 92 119 174 153 70 95 61 76 86 8 167 121 71 58 101 177 14 36 69 158 90 64 82 104 55 62 90 165 109 175 23 29 195 94 3 138 48 21 154 106 161 100 144 79 23 17 102 48 9 47 90 10 6 175 94 190 192 127 112 122 13 37 68 164 198 110 6 187 65 159 199 116 78 181 69 84 1 176 197 99 40 81 72 86 121 25 123 91 44 118 107 165 198 105 107 126 12 31 5 194 62 120 76 22 163 63 152 126 157 153 102 50 109 75 5 26 199 73 90 9 88 101 121 149 13 176 169 2 106 107 84 73 26 152 72 88 62 145 51 120 166 58 181 102 94 57 186 93 114 62 87 160 65 121 8 46 109 23 199 54 71 83 118 192 62 81 155 196 60 149 146 61 92 134 56 166 29 129 148 75 122 150 165 3 80 161 136 191 82 173 87 188 93 150 101 195 147 97 191 182 156 189 124 134 22 97 77 27 160 76 70 94 15 105 47 131 91 168 2 162 152 196 111 168 76 136 92 147 1 149 11 163 70 175 170 4 142 26 40 107 114 122 59 76 63 8 197 59 176 112 110 33 161 87 6 84 197 109 17 196 97 153 96 132 143 119 147 148 170 184 62 103 191 200 85 110 27 69 50 191 152 160 183 84 147 33 131 4 44 4 185 153 52 155 7 83 189 130 62 56 2 37 149 57 133 121 128 133 52 199 60 151 140 163 157 151 137 179 184 1 51 159 67 187 172 127 47 54 191 14 31 183 155 26 112 83 124 188 91 19 116 148 88 195 77 77 103 112 74 167 83 59 150 195 14 72 171 20 183 169 78 103 13 77 64 92 108 37 7 1 118 67 108 174 171 78 181 139 190 190 159 102 23 38 68 93 150 198 90 74 171 156 153 52 144 170 30 42 1 85 46 28 65 124 27 49 111 37 49 127 56 100 38 155 166 160 110 61 166 199 103 158 16 140 15 152 140 198 183 13 2 86 128 157 11 164 54 92 122 91 44 92 27 90 86 61 62 95 163 75 190 154 137 195 78 180 94 139 185 1 18 90 15 86 96 118 30 5 5 26 184 56 87 155 113 155 71 38 130 77 162 70 179 89 162 55 110 62 101 100 111 159 54 5 4 77 58 116 2 173 152 172 70".split()))

# dp[i][j] : Sの左からi文字目までと Tの左からj文字目まででの 共通部分文字列の数
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N+1):
    for j in range(M+1):
        if 0<=i-1 and 0<=j-1 and S[i-1]==T[j-1]:
            dp[i][j] += dp[i-1][j-1]
        if 0<=i-1:
            dp[i][j] += dp[i-1][j]
        if 0<=j-1:
            dp[i][j] += dp[i][j-1]
        # 重複カウント部分を減算する
        if 0<=i-1 and 0<=j-1:
            dp[i][j] -= dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[N][M])

Submission status: Wrong Answer

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
L = input().rstrip()

lenL = len(L)
mod = 10**9+7

dp0 = [0]*(lenL+1) # dp0[i] : 上からi桁目まで L と一致する (A,B) の場合の数
dp1 = [0]*(lenL+1) # dp1[i] : 上からi桁目までで L と一致しない (A,B) の場合の数

dp0[0] = 1

for i,l in enumerate(L, 1):
    # 現在の桁が 0 の時
    if l=="0":
        dp0[i] = dp0[i-1]   # (0,0) のみ
        dp1[i] = dp1[i-1]*3 # (0,0), (0,1), (1,0) の3通り
    # 現在の桁が 1 の時
    else:
        dp0[i] = dp0[i-1]*2 # (0,1), (1,0)
        dp1[i] = dp0[i-1] + dp1[i-1]*3 
        # (i-1)桁まで一致している場合, (0,0) のみ
        # (i-1)桁まで一致していない場合, (0,0), (0,1), (1,0) の3通り
    dp0[i] %= mod
    dp1[i] %= mod

print((dp0[-1] + dp1[-1]) % mod)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    if s[0] != t[0]:
        dp[0][1] = 1
        dp[1][0] = 1
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] + 1)%MOD
            else:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j])%MOD
    if s[-1] == t[-1]:
        dp[-1][-1] += 1
    print(dp[-1][-1])

if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mod=10**9+7
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=(2*dp[i][j]+1)%mod
        else:
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]
            dp[i+1][j+1]%=mod            
print(dp[n][m]+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mod=10**9+7
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=(2*dp[i][j]+1)%mod
        else:
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]
            dp[i+1][j+1]%=mod            
print(dp[n][m]+1)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
def main():
    t = [int(t)for t in input().split()]
    n,m = t[0],t[1]

    s = [int(z)for z in input().split()]
    t = [int(z)for z in input().split()]
    
    dp = [[0]*(m+1)for _ in range(n+1)]
    dpsum = [[0]*(m+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(m):
            dpsum[i+1][j+1] = dpsum[i+1][j] + dpsum[i][j+1]
            if s[i] == t[j]:
                dpsum[i+1][j+1] += 1
    print((dpsum[n][m]+1) % (10**9+7))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 22:10-
# pdf has been seen.

n, m = map(int, input().split()) 
s = list(map(int, input().split())) 
t = list(map(int, input().split())) 

MOD = 1000000007

s = [[0] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    if i > 0:
      s[i][j] += s[i-1][j]
      s[i][j] %= MOD

    if j > 0:
      s[i][j] += s[i][j-1]
      s[i][j] %= MOD

    if si == tj:
      s[i][j] += 1
      s[i][j] %= MOD
    elif i > 0 and j > 0:
      s[i][j] -= s[i-1][j-1]
      s[i][j] %= MOD

print((s[n-1][m-1] + 1) % MOD)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0 for _ in range(M)] for _ in range(N)]
dp[0][0] = 1

for i in range(N):
  for j in range(M):
    if i == j == 0:
      continue
    if S[i] == T[j]:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % MOD
    else:
      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
      
print(dp[-1][-1] + 1)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    a = [[1 if i==j else 0 for j in t] for i in s]
    u = [0] * m
    for i in range(n):
        c = a[i]

        for j in range(1,m):
            c[j] += u[j-1]

        e = c[:]
        for j in range(1,m):
            e[j] += e[j-1]
            e[j] %= mod

        if i > 0:
            for j in range(m):
                e[j] += u[j]
                e[j] %= mod
        u = e

    r = sum(map(lambda x: sum(x) % mod, a)) + 1

    return r % mod


print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    S=list(map(int,input().split()))
    T=list(map(int,input().split()))
    C=[[0]*(m+1) for _ in range(n+1)] # dp の累積和を持つ
    for i in range(n): C[i][0]=1
    for j in range(m): C[0][j]=1

    for i in range(n):
        for j in range(m):
            if(S[i]==T[j]): C[i+1][j+1]+=C[i][j]
            C[i+1][j+1]+=C[i+1][j]+C[i][j+1]-C[i][j]
            C[i+1][j+1]%=MOD

    print(C[-1][-1]+2)
resolve()

Submission status: Wrong Answer

Solution code:
def main():

    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

    dp0 = [[0] * 2005 for _ in range(2005)]
    dp1 = [[0] * 2005 for _ in range(2005)]

    dp0[0][0] = 1
    for i in range(N + 1):
        for j in range(M + 1):
            dp0[i + 1][j] += dp0[i][j]
            dp1[i][j] += dp0[i][j]
            dp1[i][j + 1] += dp1[i][j]
            if i < N and j < M and S[i] == T[j]:
                dp0[i + 1][j + 1] += dp1[i][j]
            dp0[i][j] %= MOD
            dp1[i][j] %= MOD

    ans = dp1[N][M]
    print (ans)
    return 

if __name__ == '__main()__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mod=10**9+7
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for i in range(n+1)]
sum=[[0 for i in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
print(sum[-1][-1]%mod)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ss = input()
ts = input()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (ss[2*i] != ts[2*j])*d[i][j]
print(d[n][m]%(10**9+7))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (0 if ss[i] == ts[j] else d[i][j])
print(d[n][m])

Submission status: Wrong Answer

Solution code:
(n,m),s,t=map(int,input().split()),input(),input()
d=[[1]*(m+1)for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1]=d[i][j+1]+d[i+1][j]-(s[2*i]!=t[2*j])*d[i][j]
print(d[n][m]%(10**9+7))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(M+1) for _ in range(N+1)]
dp[0][0] = 1
Sum = [[1]*(M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = Sum[i-1][j-1]
        else:
            dp[i][j] = 0
        Sum[i][j] = Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+dp[i][j]
print(Sum[N][M])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]
p = 10 ** 9 + 7
DP = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
for i in range(N + 1):
  DP[i][0] = 1
for j in range(M + 1):
  DP[0][j] = 1
for i in range(N):
  for j in range(M):
    DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j]
    if S[i] == T[j]:
      DP[i + 1][j + 1] += DP[i][j]
    DP[i + 1][j + 1] %= p
  print(DP[i])
print(DP[N])
print(DP[N][M])

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil

def input():
    return sys.stdin.readline().strip()

def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def rinput():
    return map(int, tinput())

def rlinput():
    return list(rinput())

def nok(a, b):
    m = a * b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return m // (a + b)    


def main():
    mod = 1e9 + 7
    n, m = rinput()
    s = rlinput()
    t = rlinput()
    a = [1] * (m + 1)
    for j in s:
        d = a[:]
        k = 0
        for i, v in enumerate(t):
            d[i] = (k + d[i]) % mod
            if j == v:
                k = (k + a[i]) % mod
        d[-1] = (k + d[-1]) % mod
        a = d[:]
    print(a[-1])
    
    
    
main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp =[[0]*m for i in range(n)]
sum_ = [[0]*m for i in range(n)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i][j] = 1
            if i!=0 and j !=0:
                dp[i][j] = dp[i][j] +sum_[i-1][j-1]
        else:
            dp[i][j] = 0
        if i!=0 and j !=0:
            sum_[i][j] = dp[i][j] + sum_[i-1][j]+sum_[i][j-1]-sum_[i-1][j-1]
        elif i==0 and j == 0:
            sum_[i][j]= dp[i][j]
        elif i==0:
            sum_[i][j] = dp[i][j] + sum_[i][j-1]
        else:
            sum_[i][j] = dp[i][j] + sum_[i-1][j]

print(sum_[n-1][m-1]+1)