J-好的序列_牛客小白月赛8

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

定义一个序列是好的，当且仅当它的所有元素的 $\gcd$ 等于1。
定义函数 f_k(N) 表示长为 k的、每个元素是[1,N] 范围内的正整数的所有N^k 个序列中，好的序列的个数。
给定 N, k，求：
$\left(\sum_{i=1}^Nf_k(i)\right)\bmod998244353$

输入描述:

两个整数N，k，含义见题面

输出描述:

一个整数，含义见题面

示例1

输入

复制

4 2

输出

复制

说明

f₂(1) = 1, f₂(2) = 3, f₂(3) = 7, f₂(4) = 11。
f₂(4)对应的 11 个长为 2 的序列分别是：(1,1),(1,2),(1,3),(1,4),(2,1),(2,3),(3,1),(3,2),(3,4),(4,1),(4,3)

示例2

输入

复制

95723 91427

输出

复制

236956841

备注:

n<=1e9,k<=1e5