{"problem":{"name":"[USACO24OPEN] Smaller Averages G","description":{"content":"Bessie has two arrays of length $N$ ($1 \\le N \\le 500$). The $i$-th element of the first array is $a_i$ ($1 \\le a_i \\le 10^6$) and the $i$-th element of the second array is $b_i$ ($1 \\le b_i \\le 10^6$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10282"},"statements":[{"statement_type":"Markdown","content":"Bessie has two arrays of length $N$ ($1 \\le N \\le 500$). The $i$-th element of the first array is $a_i$ ($1 \\le a_i \\le 10^6$) and the $i$-th element of the second array is $b_i$ ($1 \\le b_i \\le 10^6$).   \n\nBessie wants to split both arrays into **non-empty** subarrays such that the following is true. \n1. Every element belongs in exactly 1 subarray. \n2. Both arrays are split into the same number of subarrays. Let the number of subarrays the first and second array are split into be $k$ (i.e. the first array is split into exactly $k$ subarrays and the second array is split into exactly $k$ subarrays). \n3. For all $1 \\le i \\le k$, the average of the $i$-th subarray on the left of the first array is **less than or equal to** the average of the $i$-th subarray on the left of the second array.   \n\nCount how many ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo $10^9+7$. Two ways are considered different if the number of subarrays are different or if some element belongs in a different subarray.\n\n## Input\n\nThe first line contains $N$.  \n\nThe next line contains $a_1,a_2,...,a_N$.  \n\nThe next line contains $b_1,b_2,...,b_N$.\n\n## Output\n\nOutput the number of ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo $10^9+7$.\n\n[samples]\n\n## Note\n\n##### For Sample 1:\nThe two valid ways are: \n1. Split the first array into $[1],[2]$ and the second array into $[2],[2]$.\n2. Split the first array into $[1,2]$ and the second array into $[2,2]$.\n\n##### For Sample 2:\nThe three valid ways are: \n1. Split the first array into $[1,3],[2]$ and the second array into $[2,2],[2]$.\n2. Split the first array into $[1,3],[2]$ and the second array into $[2],[2,2]$.\n3. Split the first array into $[1,3,2]$ and the second array into $[2,2,2]$.  \n\n##### For Sample 3:\nThe only valid way is to split the first array into $[2],[5,1,3],[2]$ and the  second array into $[2],[1,5],[2,2]$.  \n\n#### SCORING:\n- Inputs 5-6: $N \\le 10$\n- Inputs 7-9: $N \\le 80$ \n- Inputs 10-17: $N \\le 300$ \n- Inputs 18-20: $N \\le 500$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10282","tags":["动态规划 DP","USACO","2024","前缀和","双指针 two-pointer"],"sample_group":[["2\n1 2\n2 2","2"],["3\n1 3 2\n2 2 2","3"],["5\n2 5 1 3 2\n2 1 5 2 2","1"],["7\n3 5 2 3 4 4 1\n5 3 5 3 3 4 1","140"]],"created_at":"2026-03-03 11:09:25"}}