using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("7");
//12
}
else if (InputPattern == "Input2") {
WillReturn.Add("441");
//94700
}
else if (InputPattern == "Input3") {
WillReturn.Add("411111111114");
//462474062
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
const long Hou = 998244353;
static long mN;
struct RangeInfoDef
{
internal long StaB;
internal long EndB;
internal long NGACnt;
}
static List<RangeInfoDef> mRangeRangeInfoList = new List<RangeInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
mN = long.Parse(InputList[0]);
long CurrB = 2;
while (true) {
RangeInfoDef WillAdd;
WillAdd.StaB = CurrB;
WillAdd.EndB = DeriveMaxB(CurrB);
WillAdd.NGACnt = DeriveNGCnt(CurrB);
mRangeRangeInfoList.Add(WillAdd);
CurrB = WillAdd.EndB + 1;
if (CurrB >= mN) {
break;
}
}
long Answer = 0;
foreach (RangeInfoDef EachRangeInfo in mRangeRangeInfoList) {
long StaB = EachRangeInfo.StaB;
long EndB = EachRangeInfo.EndB;
long NGACnt = EachRangeInfo.NGACnt;
long Syokou = mN - (StaB + 1) + 1;
long Makkou = mN - (EndB + 1) + 1;
long KouCnt = EndB - StaB + 1;
long TousaSuuretuSum = DeriveTousaSuuretuSum(Syokou, -1, KouCnt, Hou);
long CurrAnswer = TousaSuuretuSum - KouCnt * NGACnt;
CurrAnswer %= Hou;
Answer += CurrAnswer;
Answer %= Hou;
if (Answer < 0) Answer += Hou;
}
Console.WriteLine(Answer);
}
// Bの現在値を引数とし、同じNGACntでの最大のBを求める
static long DeriveMaxB(long pMinB)
{
long BaseNGCnt = DeriveNGCnt(pMinB);
long L = pMinB;
long R = mN - 1;
if (DeriveNGCnt(R) == BaseNGCnt) {
return R;
}
while (L + 1 < R) {
long Mid = (L + R) / 2;
if (DeriveNGCnt(Mid) == BaseNGCnt) {
L = Mid;
}
else {
R = Mid;
}
}
return L;
}
// Bを引数とし、B超えでNGなAの数を返す
static long DeriveNGCnt(long pB)
{
// 2倍がN超えの場合
if (pB * 2 > mN) return 0;
long Syou = mN / pB;
return Syou - 2 + 1;
}
// 初項と公差と項数と法を引数として、等差数列の和を返す
static long DeriveTousaSuuretuSum(long pSyokou, long pKousa, long pKouCnt, long pHou)
{
pKouCnt %= Hou;
long Makkou = pSyokou + pKousa * (pKouCnt - 1);
Makkou %= Hou;
long wkSum = (pSyokou + Makkou) % Hou;
wkSum %= Hou;
long Result = wkSum * pKouCnt;
Result %= Hou;
Result *= DeriveGyakugen(2);
Result %= Hou;
return Result;
}
// 引数の逆元を求める
static Dictionary<long, long> mMemoGyakugen = new Dictionary<long, long>();
static long DeriveGyakugen(long pLong)
{
if (mMemoGyakugen.ContainsKey(pLong)) {
return mMemoGyakugen[pLong];
}
return mMemoGyakugen[pLong] = DeriveBekijyou(pLong, Hou - 2, Hou);
}
// 繰り返し2乗法で、(NのP乗) Mod Mを求める
static long DeriveBekijyou(long pN, long pP, long pM)
{
long CurrJyousuu = pN % pM;
long CurrShisuu = 1;
long WillReturn = 1;
while (true) {
// 対象ビットが立っている場合
if ((pP & CurrShisuu) > 0) {
WillReturn = (WillReturn * CurrJyousuu) % pM;
}
CurrShisuu *= 2;
if (CurrShisuu > pP) return WillReturn;
CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
}
}
}
{a,b,c}が全て1以上N以下で
{a,b,c}はdistinctでなければならないので、
b > a は bとcが等しくなりNGです。
b = a は cが0になりNGです。
よって b < a が必要条件です。
bを全探索し、NGなaの数に注目します。
N=100とし、[1,100]なbを全探索します。
b= 1 なら [ 2,100]でNGなAは、 1*2 〜 1*100
b= 2 なら [ 3,100]でNGなAは、 2*2 〜 2* 50
b= 3 なら [ 4,100]でNGなAは、 3*2 〜 3* 33
b= 4 なら [ 5,100]でNGなAは、 4*2 〜 4* 25
b= 5 なら [ 6,100]でNGなAは、 5*2 〜 5* 20
b= 6 なら [ 7,100]でNGなAは、 6*2 〜 6* 16
b= 7 なら [ 8,100]でNGなAは、 7*2 〜 7* 14
b= 8 なら [ 9,100]でNGなAは、 8*2 〜 8* 12
b= 9 なら [10,100]でNGなAは、 9*2 〜 9* 11
b=10 なら [11,100]でNGなAは、10*2 〜 10* 10
b=11 なら [12,100]でNGなAは、11*2 〜 11* 9
b=12 なら [13,100]でNGなAは、12*2 〜 12* 8
b=13 なら [14,100]でNGなAは、13*2 〜 13* 7
b=14 なら [15,100]でNGなAは、14*2 〜 14* 7
b=15 なら [15,100]でNGなAは、15*2 〜 15* 6
[b,N]でのNGなAの数は、
bに対し広義単調減少なので、連続区間は二分探索することができます。
候補なAの数の個数は、等差数列の和の公式で求めることが可能なので、
構造体{StaB , EndB , NGなAの数} のListを作成し、
解くことができます。