#P3491. PA2007 Subsets

    ID: 2703 传统题 8000ms 128MiB 尝试: 54 已通过: 12 难度: 8 上传者: 标签>CF2500省选/NOI-独立集普通生成函数生成函数求系数Pascal 递推截断幂级数快速幂NTT任意模数卷积中国剩余定理

PA2007 Subsets

题目描述

有一个集合 U={1,2,…,n}U = \left\{ 1,2,\dots, n\right\}, 要从中选择 kk 个元素作为一个子集 AA. 若 a∈Aa \in A, 则要求 a∗X∉Aa * X \notin A, 其中 XX 是一个给定的数.

求可选方案对 mm 取模后的值.

输入格式

第一行共四个整数,分别为题面描述中的 n,m,k,Xn, m, k, X

输出格式

共一行一个整数,为可选方案对 mm 取模后的值.

样例输入

6 1234 3 2

样例输出

9

数据范围

对于所有数据, 满足 $1 \leq n \leq 10^{18}, 2 \leq m \leq 10^6, 0 \leq k \leq 1000, 2 \leq X \leq 10$.