T44250 日常

泷打工的餐厅正在举行摆盘大赛，你能帮助泷拿到尽量高的奖金吗？泷拿到奖金后会请三叶和你喝咖啡的！

餐厅提供了$n$个盘子，分别编号为$1,2,\cdots,n$。把它们排成一行，排好后第$i(1\le i \le n)$个盘子的编号为$a_{i}$，此时称序列$a_{1},a_{2}, \cdots ,a_{n}$为一种摆法，也就是说每一种摆法恰为$1$~$n$的一个排列。如$3$个盘子的不同摆法有$1,2,3$，$1,3,2$，$2,1,3$，$2,3,1$，$3,1,2$，$3,2,1$六种。 两种摆法比较大小的方法如下：首先比较第$1$个盘子的序号；如果第$1$个盘子的序号相同，则再比较第$2$个盘子的序号；如果第$2$个盘子的序号也相同，再比较第$3$个盘子的序号……依此类推。我们称这种比较摆法大小的方法为按字典序比较。上面列举的$3$个盘子的所有摆法就是按照字典序从小到大给出的。 餐厅主管喜欢不同寻常的摆法。他定义摆法$a$的“错乱数”为摆法$a$中满足$a_{i}\neq i$的$i$的数量，如摆法$1,2,3$的错乱数为$0$，摆法$1,3,2$的错乱数为$2$，摆法$3,2,1$的错乱数也为$2$。根据自己的喜好，餐厅主管对每一个错乱数$k(0\le k \le n)$设置了基础奖金$c_{k}$。 摆盘大赛的规则如下：选手选定某一个错乱数$k$，按字典序从小到大摆出**所有**错乱数为$k$的摆法，如果他摆出的摆法共有$d$种，那么他得到的奖金为$m=c_{k}\times d$。当然，餐厅主管的钱有限，最终发放的奖金为$m\ mod\ 993244853$的值。 例如，餐厅主管提供了$3$个盘子，且设定$c_{3}=2$；选手A选定错乱数$3$，按字典序摆出$2,3,1$，$3,1,2$这两种错乱数为$3$的摆法（$d=2$），则他最终得到的奖金为$c_{3}\times d=2\times 2=4$。 现在泷想拿到最高的奖金。请你帮他找出$k$，使得他最终得到的奖金最多，并告诉他奖金的最大值和错乱数为$k$的字典序最小的摆法。如果有$k_{1}

输入共$2$行。 第$1$行有$1$个正整数$n$，表示餐厅提供的盘子的数目。 第$2$行有$n+1$个非负整数，第$k(0\le k \le n)$个整数$c_{k}$表示所选错乱数为$k$时的基础奖金。

设选定错乱数为$k$时，最终得到的奖金最大。$k$不必输出。 输出共$2$行。 第$1$行有$1$个非负整数，表示**最终得到**的奖金的最大值。 第$2$行有$n$个正整数，表示错乱数为$k$，且字典序最小的摆法。

对于5%的数据，满足除$c_{0}\neq 0$外，所有$c_{k}=0(k>0)$。 对于另外25%的数据，满足$n\le 12, c_{k}\le 100000$。 对于另外30%的数据，满足$n\le 500000$。 对于另外40%的数据，满足$n\le 1000000$。 对于100%的数据，满足$c_{k} \le 10^{9}$。  ----- 样例1解释：当$k=2$时，所有摆法按字典序从小到大列举为$1,3,2$，$2,1,3$，$3,2,1$，共3种（$d=3$），则$m=c_{2}\times d=3\times 3=9$。 样例2解释：当$k=0$时，所有摆法按字典序从小到大列举为$1,2,3$，$d=1$，则$m=c_{0}\times d=4\times 1=4$。 样例3解释：当$k=3$时，所有摆法按字典序从小到大列举为$2,3,1$，$3,1,2$，$d=2$，则$m=c_{3}\times d=4\times 2=8$。