正整數的冪次


Submit solution

Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

想必大家都知道 \(2^4=4^2,3^2=9^1,3^6=27^2\) 等正整數的冪次之間相等的關係。你有沒有想過底數和指數在某個範圍以內的正整數冪次到底有幾種呢?

給定正整數 \(n,m\),定義集合 \(S=\{x^y\ |\ x,y\in\mathbb{N},1\le x\le n,1\le y\le m\}\)。

問題很簡單,請計算 \(|S|\bmod 998244353\)。

Input

輸入只有一行,這行輸入兩個正整數 \(n,m\ (1\le n,m\le 10^{14})\)。

Output

輸出一個整數,代表 \(|S|\bmod 998244353\)。

Constraints

第 \(1\) 組測資:\(1\le n,m\le 10\)。(\(1\%\))

第 \(2\) 組測資:\(1\le n,m\le 500\)。(\(7\%\))

第 \(3\) 組測資:\(1\le n,m\le 10^6\)。(\(22\%\))

第 \(4\) 組測資:\(1\le n\le 10^6\)。(\(43\%\))

第 \(5\) 組測資:無特別限制。(\(27\%\))

Sample Input 1
4 4
Sample Output 1
11
Sample Input 2
48763 45510
Sample Output 2
216698900

Comments

There are no comments at the moment.