Maximizing Convenience in Kolar City

After winning the selection, Kiana became the mayor of Kolar City. To fulfill her election promise, she plans to construct a metro system connecting the n important landmarks of the city. In Kolar City, it is technically possible to build a metro track between any pair of landmarks. However, too many metro lines passing through one landmark will greatly increase its congestion. Accordingly, Kiana defines the convenience of a landmark that is traversed by d metro tracks as

$$f(d)\bmod 59393$$

where $$f(x)=\sum_{i=0}^{k}a_i x^i\,.$$

Because building metro tracks is costly, Kiana wants to use as few tracks as possible while ensuring that every pair of landmarks remains connected by the metro network. Hence, the network must be a tree (i.e. it contains exactly n − 1 edges). Under these conditions, Kiana wishes to know what construction scheme can maximize the sum of the convenience values over all landmarks.

Note: The convenience of each landmark is calculated independently (by applying modulus 59393 to the value of f(d)), and then the sum is taken.

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 10⁵, 0 ≤ k ≤ 10), where n is the number of landmarks and k is the degree of the polynomial.

The second line contains k + 1 integers: a₀, a₁, ... , a_k (each |a_i| ≤ 10⁴), which are the coefficients of the polynomial f(x)= a₀ + a₁x + ... + a_kx^k.

You may assume that the input is given in a format that allows the construction of a tree spanning all landmarks.

outputFormat

Output a single integer, the maximum possible sum of convenience values over all landmarks. For each landmark with degree d, its convenience is computed as $$f(d)\bmod 59393.$$ The answer is computed by designing a tree (with exactly n − 1 edges) that connects all landmarks such that the summed convenience is maximized.

sample

1 2
1 2 3

1