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

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

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

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

(\sum_{i = l}^{r} d(i^k)) \bmod 998244353

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

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

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

| 测试点编号 | r | k |

| -----------: | -----------: | -----------: |

| 1 | \le 100 | =1 |

| 2 | \le 100 | =1 |

| 3 | \le 100 | =1 |

| 4 | \le 1000 | =1000 |

| 5 | \le 1000 | =1000 |

| 6 | \le 1000 | =1000 |

| 7 | \le 10^{12} | =10000000 |

| 8 | \le 10^{12} | =10000000 |

| 9 | \le 10^{12} | =10000000 |

| 10 | \le 10^{12} | =10000000 |