时殒·残篇
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

【题目背景】
\hspace{15pt}推开沉重的石门，MuQ 眼前出现了一个略显陈旧的实验室。
\hspace{15pt}实验室中央静静矗立着一台老式机器，金属外壳上刻着三个斑驳的大字——“时光机”。
\hspace{15pt}MuQ 心跳加速，小心翼翼地坐进驾驶舱，按下启动按钮。然而，机器只是发出一声无力的嗡鸣，随后归于沉寂。
\hspace{15pt}“果然没这么简单……”他叹了口气。目光扫过控制台，忽然发现角落里放着一本笔记本，写着：《飞羽的日记》。
\hspace{15pt}翻开泛黄的纸页，MuQ 渐渐了解了这位发明家的故事。飞羽穷尽一生心血研制时光机，就在即将成功之际，却被一道复杂的式子难住了。
\hspace{15pt}日记的最后一页写道：“真遗憾啊，只差最后一步了……这个公式的答案，或许我这辈子都等不到了吧。为了防止它落入恶势力的手中，我决定将实验室封存。希望有一天，真正需要它的人能找到这里，完成我的心愿。”
\hspace{15pt}MuQ 在日记本的最后一页找到了这个式子：给定 n，d 和 p，你需要对以下式子求值：

\displaystyle\left(\sum_{\substack{i=1\\ \gcd(i,n)=d}}^n \sum_{j=1}^i\sum_{\substack{k=1\\ \gcd(k,i)=j}}^ik^p\right)\ \bmod\ 998\,244\,353

\hspace{15pt}求出这个式子，便能补上时空机的最后一块拼图。你能解开时间的秘密吗？

输入描述:

\hspace{15pt}在一行上输入三个整数 n,d,p \left(1\leq d\leq n\leq10^8;\,1\leq p \leq 10^4\right)。

输出描述:

\hspace{15pt}输出一个整数，表示式子的结果。
示例1

输入

复制 
9 1 5

输出

复制 
96543
示例2

输入

复制 
100 4 50

输出

复制 
641597676