题目描述

在一个奇幻的王国中，存在着一个名叫小码哥的魔法师。小码哥手下收藏着 $n$ 个傀儡，他靠着手下的傀儡演出赖以生存。因此，傀儡的魅力度与他的生存息息相关。他为每个傀儡都进行了编号，即从 $1$ 到 $n$。对于编号为 $k$ 的傀儡，假设存在有序整数对 $(a,b,c)$ 满足 $1 \le a,b,c \le k$ 且 $a*b*c=k$，那么编号为 $k$ 的傀儡的魅力度定义为满足上式的所有有序整数对的个数之和。现在，他想知道他手下所有的傀儡的魅力度之和是多少，只有这样，他才能知道下周是否有饭吃。请将结果除以 $3333$ 求余。

输入格式

输入包含一个整数 $n$（$1 \le n \le 10^{12}$），表示小码哥手下收藏着 $n$ 个傀儡。

输出格式

输出一行一个整数表示小码哥手下所有的傀儡的魅力度之和除以 $3333$ 所得的余数。

3

7

解释 #1

样例解释： 对于 $k=1$ 的傀儡，存在如下序列的 $(a,b,c)$，即 $(1,1,1)$

对于 $k=2$ 的傀儡，存在如下序列的 $(a,b,c)$，即 $(2,1,1),(1,2,1),(1,1,2)$

对于 $k=3$ 的傀儡，存在如下序列的 $(a,b,c)$，即 $(3,1,1),(1,3,1),(1,1,3)$

最终输出结果为 $1+3+3=7$。