Sum Over Derangements with Cycle-Dependent Polynomial Weight

Let \( \text{cyc}_\pi \) denote the number of cycles in the cycle decomposition of a permutation \( \pi \) of length \( n \). Given two integers \( n \) and \( k \), and a polynomial \( F(x) \) of degree \( k-1 \) (with \( k \) coefficients), compute

[ S = \sum_{\pi}; F(\text{cyc}_{\pi}), ]

where the summation is taken over all derangements \( \pi \) of \( \{1,2,\dots,n\} \), that is, permutations with no fixed point (i.e. there is no index \( i \) such that \( \pi_i=i \)). The polynomial \( F(x) \) is given by

[ F(x)=a_0+a_1 x+\cdots+a_{k-1}x^{k-1}. ]

Your task is to output the integer value \( S \). You may assume that \( n \ge 1 \); note that for \( n=1 \) there is no derangement so \( S=0 \).

inputFormat

The input consists of two lines:

• The first line contains two integers \( n \) and \( k \) (the length of the permutation and the number of coefficients, respectively).
• The second line contains \( k \) space‐separated integers: \( a_0, a_1, \dots, a_{k-1} \), representing the coefficients of the polynomial \( F(x) = a_0+a_1 x+\cdots+a_{k-1}x^{k-1}. \)

outputFormat

Output a single integer \( S \) which is the sum of \( F(\text{cyc}_\pi) \) over all derangements \( \pi \) of \( \{1,2,\dots,n\} \).

sample

4 2
1 1

21