分数: 700 点
问题陈述
高桥有一座塔,分为 N 层。 最初,所有层都是未着色的。高桥打算将其中一些层涂成红色、绿色或蓝色,以形成一座美丽的塔。 他定义了 塔之美 如下:
- 塔的美丽是所有塔的分数总和 N 层,其中层的分数为 A 如果图层被涂成红色, A+B 如果图层被漆成绿色, B 如果图层被涂成蓝色,并且 0 如果图层未着色。
在这里, A 和 B 是预先给定的正整数常数。另请注意,一个图层不能涂上两种或多种颜色。
高桥正计划对塔进行粉刷,使塔的美丽变得准确 K。 这样的塔画方法有多少种?求计数模数 998244353。 当存在一个以不同颜色绘制的图层,或者以一种方式绘制某种颜色而不以另一种方式绘制的图层时,两种绘制塔的方法被认为是不同的。
约束
- 1 ≤ N ≤ 3×10^5
- 1 ≤ A,B ≤ 3×10^5
- 0 ≤ K ≤ 18×10^{10}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A B K
输出
打印绘制瓷砖的方式数,模数 998244353.
示例输入 1
4 1 2 5
示例输出 1
40
在这种情况下,红色层值得 1 分,绿层值得 3 点和蓝层值 2 点。塔的美丽之处在于 5 当我们有以下一组绘制图层时:
- 1 绿色, 1 蓝色
- 1 红色, 2 布鲁斯
- 2 红, 1 绿色
- 3 红, 1 蓝色
生产它们的方式总数是 40.
示例输入 2
2 5 6 0
示例输出 2
1
塔的美丽在于 0 仅当所有图层均未着色时。因此,答案是 1.
示例输入 3
90081 33447 90629 6391049189
示例输出 3
577742975