

Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 点
問題文
正整数 が与えられます。
となる正整数からなる長さ の数列 が何通りあるかを で割った余りを求めてください。
ただし、数列 と が異なるとは、ある が存在して であることをいいます。
制約
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
条件を満たす正整数からなる数列が何通りあるかを で割った余りを出力せよ。
入力例 1Copy
2 6
出力例 1Copy
4
の 通りの数列が条件を満たします。
入力例 2Copy
3 12
出力例 2Copy
18
入力例 3Copy
100000 1000000000
出力例 3Copy
957870001
Score : points
Problem Statement
You are given positive integers and .
How many sequences of length consisting of positive integers satisfy ? Find the count modulo .
Here, two sequences and are considered different when there exists some such that .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the number of the sequences consisting of positive integers that satisfy the condition, modulo .
Sample Input 1Copy
2 6
Sample Output 1Copy
4
Four sequences satisfy the condition: and .
Sample Input 2Copy
3 12
Sample Output 2Copy
18
Sample Input 3Copy
100000 1000000000
Sample Output 3Copy
957870001