在古老的神秘国度中，有一座由数字能量构成的城市，这座城市的安全依赖于一位智者——门泰特。每年的金秋十月，城市的屏障会因为神秘力量的周期性波动而变得脆弱，需要重新计算和加固。智者必须利用古老的数字法则来强化这个屏障，确保城市的安全。

法则是这样的：智者需要选择一个数字区间$[l, r]$，然后计算这个区间内每一个数字的 $k$ 次幂的因子数量，最后将所有这些结果加总起来。为了使屏障的能量达到最优状态，这个总和需要对 $998244353$ 取模，以此生成一个强大的魔法数字。

今年，智者选择了一个特别的区间，并决定利用这个法则进行计算。然而，这不仅仅是数学计算，每一个数字和它的因子都承载着特殊的意义和力量。城市的居民们都在期待智者的成功，因为只有他能够解开数字的秘密，保护他们免受外界的威胁。

智者现在面临着一个挑战，他需要你的帮助来完成这个计算。更形式化地说，给定 $l, r, k$，你的任务是计算下面式子的值：

其中 $d(n)$ 表示正整数 $n$ 的约数个数。

输入格式

第一行包含三个整数 $l, r, k$。

输出格式

输出一行一个整数，即答案。

1 5 1

10

1 10 2

48

1 100 3

2302

提示

保证$r-l \le 10^6$