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: Accepted

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAAx5Nl8C/+19D3xUxbX/3c2/5U+yCyKGP8KiCyYoIQkBkoC4CVm4KxuMJPBQwctmsyGrm93t7t0AttbYBMt2iaWtz8fray319fVhn1Ze/VPrayGIJNTX9iFV5I8oWIENIRCxILbK/s6Zmbt7781eCOj7/T6/z8dVMnu+d+bMmTNnzpyZvffOIzbHAr1Ox0kfPTePI9RYK6GtDLe2JbIAVsoNgb8TuQlcJtDp8nycVZFeZKyl1MDypbFypXpKl+qtinQ8yyelOlmawck/VkX617s5Rcpx5kQ5lDVvBUXzVqxSpK2M6bZMZTk9K9e/kqL9K1cpUk7PKVKpfensXx3D61i7pLSK5auS5cdPzXGxgejTwVrlsCrSJ1i+J1Tl7oZymdzgPyaWLmH1aenlQBqnSKV+mO711M8qme5tmOb1+MJrp60tnTVtVklByF9QTGQysbwLFy9N9LdeJvMohuH1Y33fte1a8NKDRy58/9bpT36v5v67T/4IrxXK+q1mQWDVpPxMHWIl8G82/Gv47Hfbf/G9ua/9yPW73cMe3STc9pFw/4b1rtEP/uOL054aH3hl1Obh89faH3w53/a2Q0sPzwPzkSnwdVxqvCI9Nf7f+tT4nzT4O3Sp8QIN/KcZqfHzGvhLGvV+Oy01flKDz2aN9s7TyP+BRr2va7TrbY38t2jk79HI/5iGnHGN/G4N/m9o9LtTo3+f0eA/Ois1Pl1D//0afF7QkHOrhjzXa+D3adR7UQPfpSHPWQ3+ezTyf6KBD9XAezX0v1Gjf9dr5N+kwb9Ww25DGnpI1+hHU2KGUH4WavB5DeSfxF3P7WF+VSq7JY3iMRX+U47iBjbPLGf4e3qKr2K45MdfAv4jALcyPpKfPsrk2TLGqpBHn0H5BBifVobPZvXyK5T4P2Ug/7Fcp5PVyypoYPo3q/hPZHinCudg3giJDa5bb8W5YhYnCKub/T4hJDqDoiBwwr2La8VSjz8k1DtD7hK7zyNWFdlaAK9bVisWzQTU44LcQbezuT7caHcBWORqcgYFMej0iCG7y2ZDnmvXCgF3MOT3Ob0ecZ3QUkg4+2cEwqLNRb57igqFasG9Fsq5RPsDNtuSWs+SOoHUtBiuCa61a531npaiYvge8ggurzMUEsR1Abfg8TX6bchkUa0404UQVFs0A9it8TS4fXDdIxKZoS1lVGJoUUpZZ7q8bmfQBleKBTu0Gv6JTtENZRu8NciiVsT6xaagf43gdftWi02COxj0B2sWQTNARqfg9Hr9LigDbXG5A6LH7yPFimYJgp8qCgQKuYNiSgGWADaDyshy2+uEukLBVjtLqFlUO0Pw0nbMwkq8btYZAMwmGioqKipLlvb4VjMeKaqqdWJ984uwsTNIY+8KuH3N/gY3U2WCY3Gil4GhNquiGY0eX4PQ6AmGRMHfaAOVNDerhBssq2LoPJffB/nCLtHW7KKaL5E07w9jDULQ6VvtFhqbRajqIZWtVhVTM7VDn8t74hqkmR10Q3+1uG3NiZ6kYtQ7GwSXMyRiRb41zUtAaWU+P70mpho78xPdlZSJCQqjoQwazUyjGS3BT82/7tp7VxoVydpK1jQ5xQE2M9huwSEadAe8Thcooxk7+NoYYUudATC3BhtjAupj44eojyq6LDHS/KuBa3KgwcXZTNFaGvIMXkPgYGTlZ8qboOHTEmWJxI1Bt3K0X6NGXCCq6LYtaaZ2VuICM/8C+g2FPKt9NjDKEurH/TMbveFQE+l89GapzPUatQh2vWTR4lphgHzFArgsWwoXA9NOM51x4NtqFxRBqogTlvrWoBdZ4g6Fm0k2F83W6IeiXKPo9oIHxMbBMBEanR4v1+j2N3KNq91iiIN6wSlLjlh0r/WIXLO72RVYxzW6vP6Qm2sm7hnBZn+Lm6t3NQcgO1bD5rxmpweqgR7lFs6fL8woKOQWOuyV85cvh+8lBcVKsqhIQZZx8K2i0i4UFcxQFlPko9+F4oKi5NfigplkRZYGq7E0SDMS3zLhbxrQWUDrCUJRA6ElZAjJjQhF00mZTG4o48KRq+mEbxrjnUYoaR2p476VmYyjaqasGwZRITcuS7qeSWIYvB7Afxf/CZgO4W7OopiT0AaumNGRR/L1uFKsYPSfn38wA3cK7mL010j+dO5eRov53zegjJ5EfXruJ5nJeOqJ7z0JVBYXZvnDYz1DUF+tLH+/QOMgXJtOk8fTMrxAvkvB4qkMtn6VPrwMny2Pp2V4oQyPyfAiGS7FiYgXy/BVMnyGDA/I8FkyXIrvEC+V4bmrKJ4liy1JvCrD9TI8T4anyfBCGZ4uw0tluHx/xyrD5fsbvAzPkuE1Mtwgw5fL8CFy/cjwoTK8SYYPk+tNhg+X4WtleLYMb5XhOTJ8gww3ytctMtwkX4fL8BEyfIsMl687tsrw62T4Nhk+Soa/IsOvl9uDDB8tt08ZfoMM3yvDc2X4ARk+RoYfleFj5XYuw8fJ18kyfLx83MnwGxUL9yQ+QT5eZPhE+bpOhsvXd7kyfJLc/mX4TXL7l+E3y+1fhlvk9i/DJ8vtX4aXye1fhk+R278Mv0Vu/zI8T27/Mjxfbv8yfKrc/mX4rXL7l+G3ye1fhs+U278Mny63fxleLm9v22kDH82w2c0cv75T1Mf38m2vG3Zx8ZmVAMUnV8Ff40QrfEO6iWwVHY3DZ3I50uiyevYSuhhpdFU9nYSeijS6qJ5thL4JaXRNPVsIPRZpdEk9mwg9Eml0RT2thB6KNIrbEyC0Hml0PT2rCP03Hmh0OT01hD6HNLqaHiuhTyGNLqankNAfII2upcdM6ENIo0vpMRF6H9LoSno4Qr+BNLqQnv5LSL+GtIm0n9CvIj2CtJ/Qv0J6JGk/oX+B9HWk/YR+GulRpP2E/iHS15P2E/r7SI8m7Sf0d5C+gbSf0N9COpe0n9APIT2GtJ/QQaTHkvYT+gGkx5H2E7oe6fGk/YS+F+kbSfsJvQTpCaT9hL4T6Ymk/Z8jXYm0mbSf0OVITyLtJ3Qx0jeR9hN6KtI3k/YT+iakLaT9hB6L9GTSfkKPRHoKaT+hhyJ9C2k/ofVI55H2E/pvC4HOJ+0n9Dmkp5L2E/oU0reS9hP6A6RvI+0n9CGkp5H2E3of0gWk/YR+A+nppP2fxeM1O96sX8XFjoNqduDey3YkX90Coyp2DLIv39VYYJzYToaUcWIVxBB99sib9/ORD/i2D/tr6uzdnYWVVo7v3tlZgUl3/1gYU9d32czcX0n+jxUMrNwrW4E1fzv+Fa97hYxUGJ5DdiAQP9q4aRcplSyzneR/9AxJdl5K4yP9/M7YHbyui3/zkjgiwSGLcVCXb719DOiXC9+wlI8cj30TFNCVkQWIbiXNqc7f+7hS3qUV/1CxrGJpRV0t/+hpA7gBPnJy+ypocqwSxgjf8Q2Lafu9C4CcgWR3lYVsX3VVWXhuB8Zh2zGQi7WAelHKPD6yk2/baeIjBr7bSuKNLqsJylnN6HEgJb62V1/Uyf8mTj+P8JEqS4098gc+4rAsxyqIx3NEvRaTI+K1BKrX94kZ9jabWeeIllgcEdGytnr9BYQWmHUyIT76nApxBx/Zzbd1ghA2bjupNnL2VXQwMQEMgu+2MVlsRBY+8qwFN/WglnBuz84sNAEZZmz/JUD26Equ6jtzduQmKmunlRnbv0947OY7QrqK1vhS3mj7mO/4rWUT1hc3Io8LxvYHgAcf/RFB+fWHje33EKbz+OiM2KG/AycQlW+bb46HJ/PROXzHfBNf1i1mxBaTa+/HFmDa3U7Kc1R4A2sECYr46ArLKh6UtQq4h6/rLYY2yCFxEnA3xMNjkfv6OHBOZ5xP/w3SKMkFbf1aJs4sD4NptD+SSbq5ScdHv2EJQCFj+88A2v4g2MZvcLoo2hd7BJm0XYRLjwMg64rGzxL2sIt2RRrfPZ/aw3y0h/msD+ZL9nCYjz7MxRZ/Go/bI918B9gZmoWVGBrKV8NHVsAfMAVois1MmvIw2KeNacqC7YicjY2H1BH5hmW5neS62Q657Ilclz7Fq2djFz5FfVZZiPLQmPLQmOLhSdAn9o4FLPdekvuT2B6SO52EJ2RE8B2ixRobYaSKN4GCqyMnxHzagzcpenDjp1TP7fIakUkuZfKHHDrkzuKQ+59svEaNBy/n8pFjfPdrOEpiH4/E2sZbsDfzaE2TFDXdxGoaK5cWxMvFEill679IS8QuUtly6Xg4SSUrzqGCllLZZmRLckdO8B0OS6kk2L0jaT2lmvVsYPW0snpKqWiXacsyVmLxxWRbHNHfWrZgd5V9Ymx/Pg2BBkteddlfje0/BWqHOWF9sU/Z2BwOYYs9stveIejsYFI6PtJu2YB1G58/wHfc9mPa3rOxb19Es+u0wyis6LIZODsMK7RPSKlOcMgW6VAB6T8G0warADd3cbzxW5kI7ozpwch19rauT+2TuuwdLRf5yDl+56k0vu01XeTNtmNZfNul0lBW0b6ep0mNf+Lz9xftM+ZlvDdJ7pvRH1cYR6Rvgj9Vm0zkr5n8LSR/reRvDfm7ivwNwN/2TeiqyJdN0pct0pdt0pdO6cte6ctR6Us/CSdfs/JtXQbj+q/HUXm/F6fYO0ZtAtjEf3IQJC2ZROUzjqjsN46A9r5m5uM7w/2Osn5x7KKO4dscut14vZvcOwFzQDpf9sfwR+jADdXgPB7/IxlpHxoff4P05ROWzcQIvBbz4o7h/4bxJXDZAgUNDvQZu9J3ICNb0WH79uPffXpkkRCI9F7fuMnetkvn0P3eoftvR1mc73hEJ65xRPbYjc/vcuj2VETToURfb3VSp0X7Il2gbZhW7Z+c4XXn+MheMr/u/NuNvO413vNa1hs/nMPnd5F59+Idk5HU9VdG0p+xt+3WVZedFjsq09L/oyJa9+pnlXPqnuPE5yqjdf/xWe9WR+SoY8hF44ZONIEoNSyQo9uhO1oRLWndgTsHOC4Msdzz6GMznHdArB61xvjo1m0QhBCH+yMo3PpwKSdmfMc2v/cGNMZfkNw2NMztOGvFawqN2/sJu9i8v+K46I7tx7RtvikeHsc8+rDWrxu4cEbsR+fpyBlFuLDRfyvNa1HlDbC8sb/Kx39ymhILaLlbVOVKWbltf1XNSuAerLE7IRaG6f3R1zGauK9iRcXKivsrhJW7dhQshPDrv+DPb27mrdyrGELH+j6GuMwH/mV7EOeV9fPhwj144S28gM4y9p2PsbYqi4HveJY4AJydiYRQ9WZWdVc7uYS+PFwjY/gR/HkV44lYm7KmFQukCw/ghQaQaPvD8Oc3x1G2pSB67G64EFsBbbRHWwwwOEYl5vVuAB23/ozUbm/7bOSaoTuKqsBHnj0HorJM249g1biOiG0+hzxm2aPLDAkW7YDJJsyZ54nLCo/mo8z9l53F+R9EKDrcu1o2jUY3sus94SFGkw0GJNdr5CPD0ASpdsCJRqlm4LvhctpSz8N8FNXczb2yyJqYh7aTTvg3bBl6QVwD8dFbwXjDeVgNYY1G3TE3nX+0G8noi+nodtr+pIudAfl7x6FVv/hRUjV85AwfeS32n8DT0QE+3BFpADsFAzSz2DIPHES7pZP0Z2cY9P6i5ag0bcZ+CJx652Ld20jdGy0YJNvLOluus+fvIXmKLkBwose6R/EyCFx87LRS77/7mOr9Ooxych1lJ0HpB6ECcCLLZWEkH3Xg1WPhoRVGU7oFdZ7NR6qJwiDGgfACvpjhiyFFWwZEnNGMb84CVxCRtJf97VnMM0Q2psv7qnUlupDfssa3W4inJhPkzI/o0MNcy6EhqFr07LE/MD3jpmRsej80Ni/R2L3naGMzbEUf9t5lj7xu/IdOaApE5SQq2YHxWezv/Tjcdtoj6RZovcEOIw9UkI+RVwZGXjpEDHZ0F3SKZE0ltuOIrDJox2it/TRGW4sp6BtMLWsTmNr2Jvjzav/tMIL++BEJAO3RuRYapzogL5HeETkZe/4sNkCL/STGfozEPrYDuFlf0vX8HAWNdBf19fyIfkv09tBYL/DsTSNYxskSRbf0l1xttzx1VqNbZvbLumXzmUSVKOUYKiU63FoSDIk3WNv7wgvRE7dSTxwO9DxDZJLFSMVnqReeCinkF/f2Xk9Yyv1HzllJFa+fwW9JhhN774PcRLOos6XKy+I8GpXNVtTYeYbW+MoZ2krpXohek5zV0DN05lmrGQ+uZXwCZ+i8s1YKVQOaRWysyO2sSCC56oEik+nqZkJidTOFZc9h2VdJ2Ws0a/hLHy1yuI8WqeGkBWCVDr08GJxxfRl+Vawonu2jK4qf9cni+54ROmZmLCwuoDXeoqjxa6xGT58sLGZ2QWJjY7sXYwssalzv1Kn7nxWf2peMkXvm0Ip7ZkgC0CB7Gq1/ioLBR6cpg57TSQaseho3GNtvSdY/Xl3/r1jxX5yWRQ895+kA6+lj6XGa4sqdrITfJ1PmAuT4FkfWwMn11qrTdL21XCaQIxKPHeijq0IpGMFJKlqKPU38rqF1LQlLfnpaMvYbTl85+Akx8Xt7ry74mcPKvdCbKvipzqYiTwaRyc5Lcnul7TQMk0/skUuy6WdeH10n3w8TPC5U2nabHJE8jJfbo6zxXz+FjX+dRkBtF40tE3B5BtP6+zDH/ek0XtxN4gK8DnM/xNjiJAhKdOHsiu9kVWywcb0jIYQoACN1RC45Ih/Efn8KtUOzgyKHdaXrBkQC9sgEvu11UyJ827Vjmg3cs48I08XG+vuxCadoj80CORpJexX7SbkQ1rd+M48zts9MQ56f8JG/89FvFpLdhCFpqt2Eol5pN+HmNMVuQu5pqqWpdjoj4zoNlmZkOwHWayYkzGy9RvcT0my4ibMCJ6Rb7dGFZrIaxFuPMd4wJVcHjZv4KGj85Hb87S3G9bJ142HlbsZmCb+d7I/tBg3AWg/KFeKkdCiGBrGLhwnTAYuItr+bgmPAD8IyGdo0rZdt7kSHWyBgwK0CcSrk0YVHG192WEwbDL3j5AtAYN/tgAV25FDsph7sJpiFIargo9Uc7SZlKEH807+TkRmGf0sN6IryUSAyQY7GCdJR9gnu9/TQyfGzGMaiTCOVpGRp7CRcBHr9Ih1j2Uz8HGg5Wg1W8gaslu7gJ73B694wvrzCJI+fHj5Fu6ZUFiwZt/9Z2naL9cUG7rj1ZidbvKmob/vXwLJ4UOSbZNMIat9PVojMYfyeDMulBvucZYbwJH79PrEYYmmyW7QqRsR+YhfdvMnuvalxE6wXkRBvIBoQS9sPi0t6W17Q0SynNikcztmT1HxPnpRtmRDN7VGGFl0nqfa2Q9p+ODxF0uD6332usX4ZhSUefR1HgHwNlMy6oErK2nNCwSO5ZNl7QloDPXaC2Vh3bBGsCbdzDivXO5ZeeyB5LQ7eJxlM4QB9GFTUS2YCIDpPYHPjsQ0x4k8TM/ZywHH7s673ETlcAXCvlTheVMmspDH9+gRVx/OYYwLmgKBsNM1mlGku/HbvAboPN0U5a7acoLOm74Tkiro5ydufAs0lDSTF/jTZF3NAfBHVESsehpuWkbftEbB6mAmM7Udw+CbD3oMn2fAtIZOiKuqFNJftTdM4dn0f7h/mGTeM1tEdi/ZdGQC/wrar7+DLdhu/XZKJwh6rjlpgXqkwOfKP8jsv6vmyGO64FhrbeokP/SMfvQeWfHOfI7/g/vQ4cZ6O/L+IOWB1bJjPAZTf+Xd9deQ06ojGL8sArI6UWOwd6U/ReLsj/ZckFO95gsq47nrUWy4f5UjTslDEaJNBtgv2wQnW7AfTUT+7EnL8M9YYSeuab0B3b2JuP1cK4iWe6yuhXM8v03ET5sOEViKncAH4inzvvhCDhj84OryWVfaOFSgrWTJAQGPv7sJcRZ1I8bg0MqBXtsrGP6uxlEwJ+DABAmulZq3HDby2Lh0fLeSjPHi3c7FhRPouReuHkHI8uipH/jnjt24lLX6RRrORjx35H+M+VA0fzePLDvHGBYfQDQ8hvmYuybrCYnZEYsR3m3Eir8E51gz+u/k43XyowRWgGc2OBJy3OHTniRc3GV+u5sCJj5YaxONQO4MdW/8XattmLL8cy9egC5c5T+tx1kPfTaO/IZCNL1BdLparcZTFRLb6rMKtfJupd8imCrrmJ/P9cjI1qFeXsMrYQBfZr5IF3b0fKqYDvux9MLDzH9AR3PcBGtrZRCFo9qjY8g/RH4Dhv6GnUbMVV/xQYSk/J0+8sTryOXwfRX6y2J3ORw70vEDmLrIcsJMZCwJ0Ph/myTP2nZf0xHb6f0OENFbtXNxhKUz8+HOHvewPDuPCYw5dv8NYeQyDl5F3dsz9N2KoASLkLvx1YHHHbS9gpZWR9BeQX1S0BMQccGqOyAU+ciq2FJQN0VM67uUb0KWP+iAR5OQ6Ik2GOztu+1cMo7AV0ADaqkgeLPr2TaGLvg3STkY0+x0CbUzfMKhF3zPHNBZ9ViJDxrqBFfhUFSSDSLZEDB8FBxmlFmxvuxQXx6MB8XzbTh0f2YN2yPNzHOBpNv7XZ2RDphrmS9ngP/4BM61GHRn8jvzz2N1PHbvM0K/DrYyxfKQSdNbD7/xUz0fuNKFnzyFBCdFz3zHUMwy9eHhFQtdbUViYwLdA2mvDn3ISY1P8GllHnCZtG/UcdbD7xGFkQM8h8tgjEzHEbvs6xHGRRwz2iN8kjhy4fSiPwX99lMTgAzL1TDiqMZWuf19xIWSTLnjxwkGYi7cvXGAFl36uqDO2+ShdSMAIxEX075VlkxN3IV4gcfGy96m15bF5LOVGo+59HGvHd8zGn1Nff49MBj1HyKznBa8JxAEya3T17KEpTxedr5LekUbunPfpyJ0Bac9PWMZoxnDLACMbYbkaK/7LexpW/BBpW8YLNw+oYOvNV7Di54+g64EVGSfm0cHYZgXLGS9fwmXEPO9J6zbhPRaPvY+rJ+JPKpbV1sCaiY8KVnS8WXSDZIY9ej9ZWNfRhW21YmWa+x5doplQx90L6Lp6qiLL+SM0S98RksVKXRfhGX4WvhTKKpsOtBnpGrrNYE9sM+xgXP6dcjGnqGgjy9JOsxSyipBfeBt8MckqMuAtPPdV3L9LweFOxqGScqBBC8vYuKkWllSx2WT+eP++nglH5LET/h5Drt8gXb/0rvo6Ca9IcLWZREeX+O4suv37DYuZ7v0+8y7uXREShw3eihI7TzD87TMy3oLLZwPb7jRB5A5zVzUMfTN2s5X4LdydNePubOQk2ZttBDl7J+FsE8DIv/swkCP5xHXcqJ1/RLFRO+o9utCwoBMna0CYZ3BRVXZQvNkegS9QmYmESL1jeNw+JKMlG+TE3c4SoykNgz40PBJQDZSb7GRKW5rSRu3bZjRxnMSj2cfM0nagI92MZfPoaMKfxzvobhjtsc2H6ZZCHh1H37Csis18N7n9Hdt8SLEtW3aENm0Z+OlUO7Kew2RHFhf5bZ1kje+ITMKZMhM9sVlHlvHgxZk3N9P1+/0GyAJrogJYEVEC9IT54+FxuL1KozQib+wQ9d9HD6GFZebB4gJcK9oDulZc/ZNNIWb0rx5iO7JolDceYqHCFjJRIXvj+ieIjSuqWM+qeBjS3jWEHe2iobEHDiU3YBsnJtUdnDhIdecfGqDurkMydecfZBWga3n2MF0DtR9GF2NN7s/g8oGaviO6xkCWng/TvSrwWC326ITqqM/gKOsNT+5dJItfsVFbD6IAaXRg7jLYy46Ikx3Rm1HlZ5nKTyr08UYsjDLtAq44/HEzJ+Y6SH3ffQexExYa2HIoMbn1nIM2sfG+ME5cwn09BQevYTwfPCCN53/A8Yy3osUmH/xC4/nJg4rx/Mk7A8dz6KBiPFcduqbxfPuBLzaeM25MGtiIGwdpYHveGWBg7gMyA9uzXzGePQcvP57/+Z3/5fGc+w4dbKZ3yHjGn1guM55P7ZeN5+r9gxvPL+2nVTy3f8B4/uH+5Hh+clxS3U+PG6S679k/QN0X9svUfc/bsvH87jt0PL/4TnI82yPv4JB2dExeNtbMLeU7pt0PaW1F5HN75IIj/zi5d3bn52mxX79Ff08yFx2WxpAj8jcIdasiZyvio96F0azjy46ET5H5dmViM3RTcsx9vIvdi0vuvqXPTcg/OtW/6Q3ulukhscHj44K34mMw3PQmf7N7us/zgGe6PyBOdwYC0wPrnKLL3+AOThP9fm9oekGL29eCbxiAK2KT3zejYPb0kEd0Tws4XQ86V7tDBA86fey6xzU9LHqgYKjJGXQ3CEF3Y0FTIMDN94e9Db5bRDM+y2Nu9HjdZq7OPDXP6fP71jX7wyGzz9nsDgFXd355ucSrvJwwKy9PcpsLLSgvZ88qlZfLHzqai88nzTPPKy+HSoJO0R+cNi8v30weJjTfV2e+3XylsitBpinXINMVi+CTqVBEwIbL5JuqFO+q2Kzk5PKXl9OH6q6xAVej1KlXq9PJoXKzIAT8IXPemiaPq8nsCZknPxTON88zi02e0LR5Ic9DbmCqvMrZp99lpnV6/D4z/E8e42ogxqNqu/yRUbMv7PWafX7R3OL0ehq4BWhrSFLL8wfNQbcTBsFqbugXscAWtwt0MTfsw0ftQCqPT7yN6oI9Bay6CCq8omVeA8+VHC1UXs6eVFVpJhSuh6/X2NDB2mPQuUZwBoPOdWrptNv7BVmv5PLgU2+ed7u5MN98B7Azz2VK9IWb3UHQgNfT7BFDcxvcLi/yyqvPB3GanWtBjmnm+nxzuTlvEPk9Ppof2Tvz4WOeMsV8k7/FHWz0+teYXU1u14M3/S85Ukl3wnRnQwPxol6/b/WVVZcoB3bT0JCHhW4z4998zuOr94d9DYLH1+BxuUN5LM3/X2oB6cTpvgbSg6QFiKDUtK/ga73XLXjYmPKEQDDRvTro9M6tWwfqhxEcdt9mBp82j1rEoO2G1akaS4MtHYBBEHDPTWqO2HKjMyTmURumzOvW3WYmIs4zT8mndq2sL1B7FaY+sFJo+TpggN9XctziomJhoeOuygqHICwWikolBjNJ+dn2u2z4kLTtCvmKZtl8LZ6g39fs9omDKzGjVnSiPhsGlb3MJj0OfWXGlc6QW5adPd/Fnof8851WxXOTEv4Mww2LrAr8IYabVTjP8FIVbmZ4zSLlezGaGI0/ZJHn9Mppqn5vh0GVb68q3xUaX7gMLYepVC7X3kVKeZMvKlLWt2Wesj7duLQ5T7BnElvfiMdxg23TH+PxdyH464QU71nrRxrb9Kd4fBSEi6aj8Th5AusYXNfjO6/i8XRYTtb0xeO4CsD7ZPD9SJsgxSe3tkEagOvbPorH24FedS4ex7tQWyF9EfDW8/E4vsemH1Ire6hUerZR99ASTrfWpBs3PMuwSZdlMrHnBg0gk/T8Wuq89PlLzDsc8kpRroU9j7vh9/G4CZfAOaYFObl3GoetMbRyd4ydM3WGhTwGWMje2VJ4Oh6fgIFwZY6pIie3Isfclva4Xt+HX02VOQYA3NJ33JfeiHWCHsiznAC36R05BvYs5Va0nxTXcMPvdZStPx7/JUfrqszJrcwxV+bkVeQUtmVuzOhIfzztu3r95pw8AueSLAb2jCbIt7l/IF/UC94G8+x/x+OT2DUBriTeyfZQjYNoLCsNX/+SJumthunpiT/E4/eBYaRvrrFyFTKZKnMKK3JKF+Z0prdlbczsyHg8/btpj+nTFhtySkHcSpmMFaihznT6njS8b2rLkXj8FD47nHu3Vd3OqhyrrKn/iZUoWluRYyWy4Y2W/Hvx+ALgm154d2rZ9hoUsunTUsu2FxSFTxuOgnZXfRCPf5oFPAN3D6q9fRla7b031QUbKgJHXSvUVdobj3+GT7S/KNcDNBhqSWvL2Eh0kGbSo2LkGuhMo2/Kw/dx4T1yhMdbV88D+6MUxx6MSTezue/qIdPjabYcc0c6yL4xg88pfCyTzylty6rOsQZJm1RdQsZYK/DZ+lFyjJH3dsV1X8cHdicYPzRz7+tGdo3n3tJn/30cty3T+K6ZO59pfMvMtWdlf8/MfS9r/OGJ3PcM2X+eyD1lMH5/IvecYcyhCdzBHOfWSdyrxuPA9ycjM+D7syNr/jiO++dRI/82ljsy6qZvj+WevZ7/eAwXzR36gzFc+xhjzxjuB2P2DKH1j6o17tNx9Y0ct0c3FL7t0+USvPwxffbWLO4Hei+QesObWVxbumlHFver9OyPs7gd6U9BfUcyDf+YxR3PhCH0aabhB1nco1m7daxdt7+hy/gwm/sf3b9Cu8+lj/gom2vL+CVc/c/M6z/N5v6S+WPd0zlcq+FDMM8Phy94F7JmZ0OBd7N/rJd0My7X2JPB3TJqQwbnm34+nftx2tCfp3P/nva2fhDXv/p89fnq89Xnq89Xn68+X32++nz1udLnKHsf+F627t821vqVUv4//Og00rWZSvpbKvonjJbeebV1NO1/6V1XJZWUlt7tJL0/XHp3k/QuK+kdT6XsurSXIL2r6/yluB/TzXrKT3oXWMBAaekdYDF2XXpn10b2EjDpXV3Su6euV7U/8S4y9r4oaT3Uqto3kt4pJr3bKm+kVYGXjrAq5O5n6RBV/ZfitD1rTVa2dqO0JEc/oz8z/r8ZT4n32Ks++1n/nmDpBZZm3kDT0SydwtJZLF3A0mUsbWRpC0sfY+mTLP05S19maRdL97P0BEsvsDQzl9XP0iksncXSBSxdxtJGlraw9DGWPsnSn7P0ZZZ2sXQ/S0+w9AJLM5n/G83SKSydxdIFLF3G0kaWtrD0MZY+ydKfs/RllnaNSW0HC+fPLzfnLa0P+8SwubSgpKBwWlGYUEXfLCotKCzJpyjn8jp9q80t7mAIf8AsKiyA/6aVKLIWFJsvaxNpMOqlcxiUuD5xfoEST+PElHh6Yhwr8YzE+FXimYlxrsSzUo6PNBh90rhS4kMS41OJD02MYyU+LOHPlPhwrjMlnp2YB5V4TsIPKnEjZ02JmxLnOijxEdyBlPhIDrdSB+LXJfytEh+V8LNKPPmecCU+OqU/SAMvKL3vUonnJvyoEh/DbXamwpPvD1fi4wZgeC9aOvdRPPX8NVAP1zEct4Xln8kMf0uFlzK8UIXfyfCACl/B8BdVuI/MIUl7kN4N+BjD+9nvM5+xiWY3w6XfUaR3Nl6Q+JQr8ak6xof9/vJLht/P8JrbKH6K4RGGbyqj+AQ2gb/A8M55SnnOMHybqt5xetT1WG5f/SpFHGDTM/5FNP+nbEI8wXDrNOYH2Xzalkb5vKni832CGxO/L0nz5WsMT/zOJsUFDC9V4XnpFK9R4fczvEmFf4fhZhX+CsOl38GkdxjGGC79Lii9q3BcBsUfUuGLGS79/ie9i7Wd4dLvf9I7GLcxXPp9UXrX4nsMz3Uo8+dkUnzrIiVewfBWFd6cmXocYbxH+ksVxz/E8IAK72C4Ou7/10zav3tV/fsrgg/0PwcZn6MqPsdJ/oF+TEt+PJdBB37yiRT+MFX+kVk0ClX728mEz0C/V5BFvYpa/jsYrpZzCeEz0B82aZwf8XUN/AnyvuEx3FaVn/yXrNTnO7ykwac8G99fOtAPDzWkzj/VgPyT85T0bt4yjfzVBAe/xPrxPvZS2iUa+ddo4E9r4BdRHv0YbotK/owhGufFDEl9boVTI/83NPCfaeA7NPAeDfzXJsQHxgNDYcEyUp/NFTK9SeuPm4am5jNTA39SA982NPU5I7gwSnmOTzbtR+m8r8Rv4hr58zTwORp49bDU55tszsH8A+OuHw+j/a62/2c0+GcOT43P1sAf18B/qoG/oIEfGJ76PJSzw1Of22LJTs2nNJuOd/U4LSd+YCx3oF6J2zT4uLJpfrXe/Br5n9bAL2ngN+dojCMN/PEcalf4GlH8uBn+lEb+Mxq4zqhxvpIx9bkzszXyv6SBX9Lib9I4/0sDv0cDf85E9VBYqRzvv9PI/54G/rkp9bk/40akPodo6ojU5/7cNSL1uT//MiJ1vb8doXGOD55WQM+gEES8n65wAFI0EBmYqXgAMmMAMptL3NIUCtcLdnJmQoErEMAzJAZ9v9P8YvudFcVlAh6kURVYsogcdjL44lWF9BSTq7m57JrKFA+izIyQCO2x0bNJLp+1BO9cHhRT6WY+qqhZV6MoqegVGlxaH/Z4RY8vVLLY73PTw2K0+PrCzYF1sxvDPrzRuKiwMehvprcXu7z2OxfXFgpJTdgW1xYLs8Ienzij2OatnSWg4HUubyioYmeT8wkFMAeUb7DNbvQH1ziDDfY6wdYYIMUDd9WWCpcTMNkWVLAkaCne5u31+Nwo5ZKkmCSTbaBcSi62RPErClcmkDNbHKWC4PHjgVPk7KGruftvEPnVt0oOpojqts1BFElxb+iVSyXvPL1y3jJlE2qvUku1V6+l2qvXUu01aan2KrRUe1VaWnaVWlp29VpaNljhXUExJIYbGwtcXIM76F7tCYnuoCA2Cy4v+JEQJwgNfmG111/v9AoNMApDgjO8lnP5mwNet+huKJhdVjY7dSahEcYOvddfAMUG13GNQWezW2gINzevgyIyihzrpsgqCAuWVFTbBNviKjy6Tli4eKlg4xnIVy3hhKp7FldU2+fDNUXhBiVADgJKzHF3LVhQa6sT6ioqHTaBHkBktcqP7ZGdZMcusGN+BHeDU3QqTqtSZfgSzs5ScMSDhgYeg6aq1H6XQB4AE8IhdwM7MknZInIGktZpdlar7JCjyx6I92U1VnaQ1cDWCg0hv9AEo9frTnmulVqIwZ9bqCopP3MqhQGkOLxNKWyZ8hAutVzax52p5Rh45JiySxq8QtDNeg1PLwRWAY+bnYOVlLyo5Es/ODBF7yQP4lLr7Aud2pbC6rHrlaqiR36p6/WtUY4ZcgbYoITzX7NwQl31fMktfZlnQaawsMueganMX1T0JZ3OOKDB5LA2pU7RYtVaTnmW4sCBQQ7CGziOB3MqqGJk0LPfVEII6KMll686WVM98uqBt5TzSsdRqnRS+GUeqnkFn584avJLcMApjnwc2Ntuf6Naq+REPVcoLLBY+AsduzmwRjztTzVn0RP91HIMPHlWNX/9Xzz0MHW3XduJtKkmBRZhqJqncbDuANehOHgRrrLTD7+E0yxT+MOEeWC8l+pEVHX7VCc0DvDXimNe1YXVRxqnOhE1hX+5tkNBU/TygLNhUwzMgYcsKzNxBaF1zaKzHlIxSNMm6Rs+LxkMcAXA310AfT9NdK5m1GpfuADXtA3TPA0coZqcoSauoGGdD/jRVAzSK+wmBQUhwDWIJpyYkX0LeEWsEoZ1AUzs8Jf0YUHQT6LdAncTi9KbGoJJCpi6XIpdJMqDhtyUh/Qd+WBVwJII6Gz2uKC8XyR/aP20LnDIXAGsK3AR9uXcfzOO/ZYj7QtK912UMmC8xv1biX1ZTnn2onR/Rh0DzAN+G1N+ilTlpfs4RAZYrlAenwO6EI/7pfLS/R6bGVAj/W6jus9L+ixm92zpVfd1xRiwgRXMZG03qO6vWsbupdKr7hMLGJT3hWnp7352T5ZUXrrP5DN2KGOLSn69Kn2Q3eMl0dL9KGvZBm0nl5Q/LUX7H2I61avuKysdobyvTK0/qf3trHyl6j61vJHK+9oyWBl1+ceZTjJV9/VtHa28/02r/yOq8tL9Mp2svClNmd+kSp9QlZfuo9jLbiSsz0tdXvr8UFVe+r2tpFJ5P56W/FtU40/6/dMqKXTo5evfqi7Pfl+2OpLtu1z9L6vKS/f9HGDlO1X6U9tPp6q8dF/MZjbwVuguX/8+jp5Lmqa6bzNvRer2GlTpexw9vzRNdV9n6YrU8qrLn2LyS+Wl37etrPw2lfxqf/aJbGzJ72fsX6kcqJmqek0yhyCvX7rPqV8YXPszVOUTv/+zZLPu8uVzVOWl3wE3Oy9fv/TB504NsvLS75FbWfncK+hvDKu/UG3XTqX/vtz9w6meKbzIylvZobd4gONdKfzPEE55PnDid9EATY+NuLz/HqFRfsy32O/qusuX/z/JXyJKAIsAAA=='
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np

def calc(S, T, a):
    MOD = 10 ** 9 + 7
    for i in range(1, a.shape[0]):
        for j in range(1, a.shape[1]):
            a[i, j] = (a[i - 1, j] + a[i, j - 1] -
                       (a[i - 1, j - 1] if S[i - 1] != T[j - 1] else 0)) % MOD


def main2():
    stdin = open('/dev/stdin')
    stdin.readline()
    S = np.fromstring(stdin.readline(), np.uint32, -1, ' ')
    T = np.fromstring(stdin.readline(), np.uint32, -1, ' ')
    a = np.ones((len(S) + 1, len(T) + 1), dtype=np.uint32)
    calc(S, T, a)
    print(a[len(S), len(T)])
'''