시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 32 21 18 62.069%

문제

A polynomial \(f(k)\) of degree \(t\) with integral coefficients is given as \(f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t\), where the coefficients \(c_0, \dots, c_t\) are all integers. Here, we are interested in the sum \(S(n)\) of \(f(0)\), \(f(1)\), ..., and \(f(n)\) for any nonnegative integer \(n\). That is, \(S(n)\) is defined by:

\[S(n) = \sum_{k=0}^{n}{f(k)} = f(0) + f(1) + \cdots + f(n)\]

The sum \(S(n)\) is a polynomial, too, but is of degree \(t + 1\) and rational coefficients. It can thus be represented by:

\[S(n) = \frac{a_0}{b_0} + \frac{a_1}{b_1}n + \frac{a_2}{b_2}n^2 + \cdots + \frac{a_{t+1}}{b_{t+1}}n^{t+1}\]

where \(a_i\) and \(b_i\) are integers that are relatively prime for each \(i = 0, 1, \dots, t+1\) or equivalently, that have no common divisor greater than 1.

Given a polynomial \(f(k)\) of degree \(t\) with integeral coeffcients \(c_0, \dots, c_t\), your program is to compute \(S(n)\) for the given polynomial \(f(k)\) and to output the following value

\[\sum_{i=0}^{t+1}{\left| a_i \right| }\]

where the \(a_i\) are determined as above for such a representation of \(S(n) = \frac{a_0}{b_0} + \frac{a_1}{b_1}n + \frac{a_2}{b_2}n^2 + \cdots + \frac{a_{t+1}}{b_{t+1}}n^{t+1}\).

You may exploit the following known identity for polynomials: for any positive integer \(d\) and any real \(x\),

\[(x+1)^d - x^d = 1 + \binom{d}{1}x + \binom{d}{2}x^2 + \dots + \binom{d}{d-1}x^{d-1}\]

where \(\binom{d}{i} = \frac{d!}{i!(d-i)!}\) for any integer \(i\) with \(0 \le i \le d\).

입력

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of only a single line containing a nonnegative integer \(t\) (\(0 \le t \le 25\)) and \(t+1\) following integers \(c_0, \dots, c_t\) with \(-10 \le c_0, \dots, c_t \le 10\) and \(c_t \ne 0\). This fully describes the input polynomial \(f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t\) of degree \(t\) with coefficients \(c_0, \dots, c_t\).

출력

Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer representing the value \(\sum_{i=0}^{t+1}{\left| a_i \right|}\).

예제 입력

3
3 1 1 1 1
5 0 -1 0 1 0 -1
5 -3 10 9 2 -7 5

예제 출력

17
6
206

힌트