{"problem":{"name":"Common Subsequence","description":{"content":"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 sub","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc130_e"},"statements":[{"statement_type":"Markdown","content":"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).\nIn how many pairs of a subsequence of $S$ and a subsequence of $T$ do the two subsequences are the same in content?\nHere 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.\nFor 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.\nSince the answer can be tremendous, print the number modulo $10^9+7$.\n\n## Constraints\n\n*   $1 \\leq N, M \\leq 2 \\times 10^3$\n*   The length of $S$ is $N$.\n*   The length of $T$ is $M$.\n*   $1 \\leq S_i, T_i \\leq 10^5$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$S_1$ $S_2$ $...$ $S_{N-1}$ $S_{N}$\n$T_1$ $T_2$ $...$ $T_{M-1}$ $T_{M}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc130_e","tags":[],"sample_group":[["2 2\n1 3\n3 1","3\n\n$S$ has four subsequences: $(), (1), (3), (1, 3)$.\n$T$ has four subsequences: $(), (3), (1), (3, 1)$.\nThere 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."],["2 2\n1 1\n1 1","6\n\n$S$ has four subsequences: $(), (1), (1), (1, 1)$.\n$T$ has four subsequences: $(), (1), (1), (1, 1)$.\nThere 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."],["4 4\n3 4 5 6\n3 4 5 6","16"],["10 9\n9 6 5 7 5 9 8 5 6 7\n8 6 8 5 5 7 9 9 7","191"],["20 20\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1","846527861\n\nBe sure to print the number modulo $10^9+7$."]],"created_at":"2026-03-03 11:01:13"}}