{"problem":{"name":"C. Hasan and his lazy students","description":{"content":"Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of leng","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10216C"},"statements":[{"statement_type":"Markdown","content":"Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of length $N$, and they must tell him how many Longest Increasing Subsequences are in the array.\n\nFor example, if the array is ($1$ $2$ $1$ $4$ $3$). The LIS's length is $3$, and it could be ($1$ $2$ $4$) or ($1$ $2$ $3$), so the answer is $2$. Note that you can't choose ($1$ $1$ $3$) because it must be a strictly increasing subsequence, and you can't choose ($1$ $2$ $3$ $4$) because you can't change the order of a subsequence.\n\nFirst line of the input will be $T$, number of test cases.\n\nEach test case starts with $N$, the size of the array, next line contain $N$ space separated integers, the array.\n\n$1 <= N <= 1000, 1 <= A_i <= 10^6$\n\nFor each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module $10^9 + 7$\n\n## Input\n\nFirst line of the input will be $T$, number of test cases.Each test case starts with $N$, the size of the array, next line contain $N$ space separated integers, the array.$1 <= N <= 1000, 1 <= A_i <= 10^6$\n\n## Output\n\nFor each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module $10^9 + 7$\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the length of the array.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a sequence of integers with $ 1 \\le a_{k,i} \\le 10^6 $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 1000 $  \n   - $ 1 \\le a_{k,i} \\le 10^6 $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n\n**Objective**  \nFor each test case $ k $, compute:  \n- $ L_k $: the length of the Longest Increasing Subsequence (LIS) of $ A_k $, where the subsequence must be strictly increasing and preserve order.  \n- $ C_k $: the number of distinct LISs of length $ L_k $ in $ A_k $, modulo $ 10^9 + 7 $.  \n\nOutput $ (L_k, C_k) $ for each test case.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10216C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}