D. 权值与下标

problem_type.default

1000ms

512MiB

대회가 끝났으므로 답안을 제출할 수 있습니다. "믄제에서 열기"를 누르세요.

Background

Special for beginners, ^_^

给定长度为 $n$ 的序列 $a_1,a_2,\dots ,a_n$ 和正整数 $m$ 。求：

$$\sum_{i_1=1}^n\sum_{i_2=1}^n\dots \sum_{i_m=1}^na_{a_{i_1}\times a_{i_2}\times\dots \times a_{i_m}}$$

输入的第一行包含两个正整数 $n,m$ 。

之后一行 $n$ 个正整数，表示 $a$ 这个序列。保证所有运算时 $a$ 的下标在 $[1,n]$ 内。

一行一个整数，表示答案对 $998244353$ 取模的值。

2 3
1 1

【样例解释】

显然，对于每个 $i_1,i_2,i_3$ ， $a_{i_1}=a_{i_2}=a_{i_3}=1$ ，因此 $a_{a_{i_1}\times a_{i_2}\times a_{i_3}}=a_1=1$ 。而总共 $8$ 种 $i_1,i_2,i_3$ 取法，因此答案是 $8$ 。

【数据范围】

子任务	分数	$n\le$	$m\leq$	特殊性质
$1$	$10$		$5$
$2$	$20$	$2\times 10^5$	$2$
$3$	$20$		$10^9$	$a_i=1$
$4$	$50$		$10^9$

对于 $100\%$ 的数据，满足 $1\le a_i\le n\le 2\times 10^5$ ， $1\le m\le 10^9$ 。