#P5237. [Lydsy2017省队十连测]中位数

    ID: 4279 传统题 1000ms 512MiB 尝试: 8 已通过: 5 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模阈值二值化组合数学加法原理乘法原理阶乘逆元预处理数论快速幂CF2500JOHNKRAM原创

[Lydsy2017省队十连测]中位数

[Lydsy2017省队十连测] 中位数

题目描述

对长度为奇数的数组 a[1…n]a[1\ldots n],定义其特征值为以下过程的结果。

令 med(x,y,z)med(x,y,z) 表示三个数的中位数。

calc(a, n):
    如果 n = 1,返回 a[1]
    对 i = 2, 3, ..., n-1:
        b[i-1] = med(a[i-1], a[i], a[i+1])
    返回 calc(b, n-2)

也就是说,每轮把每个连续三个数的中位数排成新数组,长度减少 22,直到只剩一个数。

给定两个整数 n,kn,k,求有多少个 1∼n1\sim n 的排列,其特征值恰好为 kk。答案对 998244353998244353 取模。

输入格式

从标准输入读入一行两个整数 n,kn,k。

输出格式

向标准输出写出一个整数,表示答案对 998244353998244353 取模的值。

样例

样例输入

3 2

样例输出

6

数据范围

nn 为奇数。

  • 对于 30% 的数据,1≤n≤101\le n\le10。
  • 对于 50% 的数据,1≤n≤1001\le n\le100。
  • 对于 70% 的数据,1≤n≤10001\le n\le1000。
  • 对于全部数据,1≤n≤10000001\le n\le1000000,1≤k≤n1\le k\le n。