题目描述

本题原名《组合与网格》，这是问题的困难版本。在这个版本中 $1\leq k,d\leq 10^{18}$。

在平面直角坐标系中，有一个由非负整数坐标点构成的网格。

网格上每个整数点 $(i,j)$ 的值定义为：

• 从原点 $(0,0)$ 出发，每次只能向右或向上移动一步，最终到达 $(i,j)$ 不同路径的方案数。

现在给定一条直线 $L$，其方程为 $y = -k \cdot x + d$，其中 $k$, $d$ 都是正整数。直线 $L$ 会经过若干网格的整数点（即坐标 $(x,y)$ 均为非负整数的点）。

请计算直线 $L$ 上所有整数点的值之和，并对 $998244353$ 取模。

输入格式

每个测试文件仅有一组测试数据。

第一行输入两个正整数 $k$ 和 $d$ ($1\leq k,d\leq 10^{18}$)。

输出格式

输出一行一个整数，表示直线 $L$ 上所有整数点的值之和对 $998244353$ 取模的结果。

2 3

3