問題一覧 > 通常問題

No.1581 Multiple Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 101
作問者 : magstamagsta / テスター : SSRSSSRS
13 ProblemId : 5581 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-30 19:07:28

問題文

正の整数 $M$ が与えられます。

以下の条件を満たす数列 $A$ は何通りあるでしょうか。総数を $10^9+7$ で割った余りを求めてください。

  • (要素数はいくつでもよい。便宜上、ここでは要素数を $N$ としておく。)
  • 要素はすべて $1$ 以上の整数である。
  • $1 \leq i \leq N-1$ を満たす任意の $i$ において、$A_{i+1}$ は $A_i$ の倍数である。
  • 要素の合計 ($A_1, A_2,…,A_N$ を足したもの) は $M$ となる。

(数列 $A$ の $i$ 個目の要素を $A_i$ と表記しています。)

入力

$M$

  • $1 \leq M \leq 10^5$
  • 入力はすべて整数である

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
6
出力
10

条件を満たす数列 $A$ は、
$\{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\}$
の $10$ 通りあります。

サンプル2
入力
1
出力
1

サンプル3
入力
82931
出力
917384154

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。