← 返回题目列表

AtCoder · agc025_b

B. RGB 着色

中文机器翻译题面 查看原题

分数: 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