No.1581 Multiple Sequence
magsta
SSRS
問題文最終更新日: 2021-06-30 19:07:28
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 302
(順位表)
の他の問題:
Problem Statement
You are given a positive integer $M$.
How many sequences $A$ satisfy the following conditions? Find the count modulo $10^9+7$.
- (The sequence may have any number of elements. For convenience, let $N$ denote the number of elements here.)
- All elements are integers greater than or equal to $1$.
- For every $i$ satisfying $1 \leq i \leq N-1$, $A_{i+1}$ is a multiple of $A_i$.
- The sum of the elements (the sum of $A_1, A_2,…,A_N$) is $M$.
(The $i$-th element of the sequence $A$ is denoted by $A_i$.)
Input
$M$
- $1 \leq M \leq 10^5$
- All inputs are integers.
Output
Output the computed value, followed by a newline.
Sample
Sample 1
Input
6
Output
10
The sequences $A$ satisfying the conditions are the following $10$:
$\{1,1,1,1,1,1\}, \{1,1,1,1,2\}, \{1,1,1,3\}, \{1,1,2,2\}, \{1,1,4\}, \{1,5\}, \{2,2,2\}, \{2,4\}, \{3,3\}, \{6\}$
Sample 2
Input
1
Output
1
Sample 3
Input
82931
Output
917384154
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。