2519: 紫色百合

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：1 Solved：0

Description

“牵着你的手的是她,路边开满了紫色的百合花......”。

你从梦中醒来，却依然忘不了梦中的百合花。一共有 NNN 朵百合花，每朵百合花都有一个权值，在二进制下正好写成一行'1'，第 iii （下标从 111 开始）朵紫色百合的权值在二进制下写成连续的 iii 个'1'。你想挑出其中一些组成 “一束百合花” 且价值在二进制下恰好为一个'1'后面 PPP 个'0'，那么有多少种挑选方案呢？

定义 “一束百合花” 的价值为这些百合花组成的集合的所有子集的权值乘积的和（空集的权值乘积算 111)。如价值为 111 和 333 组成的一束百合花价值为 1+1+3+1∗3=81+1+3+1*3=81+1+3+1∗3=8。

Input

一行两个正整数 N,PN,PN,P，含义如题目中所示。

Output

一个整数代表方案数模 998244353998244353998244353 的结果。

Sample Input Copy 

样例输入1
3 3
样例输入2
233 666

Sample Output Copy 

样例输出1
2
样例输出2
572514965

HINT

样例解释 1

第一种选取方法选取第 1,21, 21,2 朵花，权值分别为 1,31, 31,3，总价值为 888。

第一种选取方法选取第 333 朵花，权值为 777，总价值为 888。

Source/Category

加入题单

算法标签：