暂无测试数据。

给定两个正整数 $n, P$，求满足以下两个条件的长度为 $n$ 的序列 $a_i$ 个数：

1. $1 \le a_i \le P$

2. 不存在 $1 \le l \le r \le n$，满足 $a_l + a_{l+1} + ... + a_r$ 是 $P$ 的倍数

由于方案数可能很大，你只需要输出方案数对 109+7 取模的值

输入格式

第一行两个正整数 $n,P$

$1 \le n, P \le 10^4$

输出格式

输出方案数对 $10^9+7$ 取模的值。

样例解释

满足条件的序列有两个：{1,1} 和 {2,2}

2 3

2