4.公式推导

题目描述

组合数 $C_{n}^{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。

举个例子，从 $1$ , $2$ , $3$ 三个物品中选择两个物品可以有 $(1,2)$ , $(1,3)$ , $(2,3)$ 这三种选择方法。

根据组合数的定义，我们可以给出计算组合数的一般公式：

C_{n}^{m}=\frac{n!}{m!(n-m)!}

其中， $n!=\prod_{i=1}^{n}i$ 。特别的，定义 $0!=1$ 。

对于给定的 $n$ 和等差数列 $a_{k}$ ，请计算：

\sum_{i=0}^{n}a_{i}C_{n}^{i}

其中，令 $a_{0}=s$ ，对于任何的 $n>0$ ，有 $a_{n}=a_{n-1}+d$ 。

一行三个整数 $n$ ， $s$ ， $d$ 。

一行一个整数，表示答案对 $998244353$ 取模。

对于 $100\%$ 的数据， $1 \leq n \leq 10^{18}$ 。

9999999 1 0

951935696