1350: #2304. 「NOI2017」泳池

Memory Limit:512 MB Time Limit:3.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

久莲是个爱玩的女孩子。

暑假终于到了,久莲决定请她的朋友们来游泳,她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险,有些地方水太深,有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。

经过初步的分析,她把这块海域抽象成了一个底边长为 NNN 米,高为 100110011001 米的长方形网格。其中网格的底边对应着她家的私人海滩,每一个 1×11\times11×1 的小正方形都代表着一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之后,她要做的就是圈出她想要的游泳场啦。

她心目中理想的游泳场满足如下三个条件:

  • 必须保证安全性。即游泳场中的每一个单位海域都是安全的。
  • 必须是矩形。即游泳场必须是整个网格中的一个 a×ba\times ba×b 的子网格。
  • 必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。

例如:当 N=5N = 5N=5 时,若测量的结果如下(因为 100110011001 太大,这儿只画出网格最下面三行的信息,其他部分都是危险的)。

Screen Shot 2017-07-22 at 4.54.14 PM.png

那么她可以选取最下面一行的 1×41\times41×4 的子海域,也可以选择第三列的 3×13\times13×1 的子海域。注意她不能选取最上面一行的 1×51\times51×5 的子海域,因为它没有与海滩相邻。

为了让朋友们玩的开心,她想让游泳场的面积尽可能的大。因此她会选取最下面那一行的 1×41\times41×4 的子海域作为最终方案。

虽然她要明天才能知道每一个单位海域是否安全,但是她现在就想行动起来估计一下她的游泳场面积有多大。经过简单的估计,她假设每一个单位海域都有独立的 qqq 的概率是安全的,1q 的概率是不安全的。她想要知道她能选择的最大的游泳场的面积恰好KKK 的概率是多少。

然而久莲对数学并不感兴趣,因此她想让你来帮她计算一下这个数值。

输入格式

输入一行四个正整数 N,K,x,yN,K,x,yN,K,x,y,其中 1≤x<y<9982443531 \leq x < y < 9982443531x<y<998244353qqq 的取值为 xy\frac{x}{y}yx

输出格式

输出一行一个整数表示答案在模 998244353998244353998244353 意义下的取值。

即设答案化为最简分式后的形式为 ab\frac{a}{b}ba ,其中 aaabbb 的互质。输出整数 xxx 使得 bxamod9982443530≤x<9982443530 \leq x < 9982443530x<998244353。可以证明这样的整数 xxx 是唯一的。

样例

输入

10 5 1 2

输出

342025319

数据范围与提示

提示

xp11modp,其中 ppp 为质数,x∈[1,p)x \in [1,p)x[1,p)

子任务

测试点编号 NNN KKK
1,2 =1=1=1 ≤1000\leq 10001000
3 ≤10\leq 1010 ≤8\leq 88
4 ≤10\leq 1010 ≤9\leq 99
5 ≤10\leq 1010 ≤10\leq 1010
6 ≤1000\leq 10001000 ≤7\leq 77
7 ≤1000\leq 10001000 ≤8\leq 88
8 ≤1000\leq 10001000 ≤9\leq 99
9,10,11 ≤1000\leq 10001000 ≤100\leq 100100
12,13,14 ≤1000\leq 10001000 ≤1000\leq 10001000
15,16 ≤109\leq 10^9109 ≤10\leq 1010
17,18 ≤109\leq 10^9109 ≤100\leq 100100
19,20 ≤109\leq 10^9109 ≤1000\leq 10001000