关于时空复杂度，可以参考这篇博客:链接
我们该如何评判一个程序的时间和空间效率？在算法竞赛中，暴力的算法会因为超时或者超内存而无法通过，只有巧妙设计的高效算法才能收获 AC 。
诚然，我们可以对某些特定的输入进行运行时间和内存的测量。但在准备写程序之前，我们只能用语句的执行次数和使用变量的多少来衡量。不妨设为当问题输入规模为时，运算的执行次数或使用内存数量。
可能是一个很复杂的表达式，幸运的是，我们不需要精确计算，并且只需要估算当较大时的大小。此时，常数大小已经不太重要，表达式的值主要由其增长最快的一项决定。例如当，当很大的时候，的值是主要由项决定的。如果是执行次数，我们称此时的时间复杂度为。
通常情况下复杂度与循环嵌套的最多次数有关，比如二重循环，复杂度就是。但不一样的情况也很常见，此时需要具体问题具体分析，例如：
bool isprime(int x)
{
for (int i=2;i<n;i++)
if (x%i==0)
return false;
return true;
}
复杂度是估计能否通过的有效方法。在本oj，评测机1s大约能执行次运算（取决于类型），对于数据范围的题目,的算法显然无法在1s内通过，但的算法就可以轻松通过。
本题需要你的算法做到的时间复杂度和的空间复杂度。
给定长度为的数组，你需要计算，答案对取模。
注：本题时限和空限是按照C++设定的，所以可能其他语言无法通过（摊手.jpg)