Problem 3540: Divisors

Task

You are given a number $N$ . You are asked to find the number of sequences $a_1, \dots, a_k$ such that $a_1 | a_2 | \dots | a_k$ (that is, $a_1$ divides $a_2$ , which divides $a_3$ , and so on), and $N = a_1 + \dots + a_k$ .

For example, if $N = 6$ , then we have the following values for $a_1, \dots, a_k$ :

$6$ ;
$1, 5$ ;
$1, 1, 4$ ;
$1, 1, 1, 3$ ;
$1, 1, 1, 1, 2$ ;
$1, 1, 1, 1, 1, 1$ ;
$1, 1, 2, 2$ ;
$2, 4$ ;
$2, 2, 2$ ;
$3, 3$ .

Hence the answer would be: $10$ .

Input data

The first line in the input data contains the number of test cases $T$ . The $T$ lines that follow contain the values of $N$ for which you must compute the answer.

Output data

Output $T$ lines, the answers for the $T$ values of $N$ you are given. Since these answers are quite large, output their remainder modulo $10^9+7$ .

Constraints and clarifications

$1 \leq T \leq 100 \ 000$ ;
$1 \leq N \leq 500 \ 000$ .

#	Points	Restrictions
1	12	$N \leq 20$
2	21	$N \leq 100$
3	33	$N \leq 1 \ 000$
4	34	No further restrictions.

Example

stdin

stdout

10
26
475702494

Explanation

The first test case is explained in the problem description. For $N = 10$ the answers are:

$10$ ;
$1, 9$ ;
$1, 1, 8$ ;
$1, 1, 1, 7$ ;
$1, 1, 1, 1, 6$ ;
$1, 1, 1, 1, 1, 5$ ;
$1, 1, 1, 1, 1, 1, 4$ ;
$1, 1, 1, 1, 1, 1, 1, 3$ ;
$1, 1, 1, 1, 1, 1, 1, 1, 2$ ;
$1, 1, 1, 1, 1, 1, 1, 1, 1, 1$ ;
$1, 1, 1, 1, 1, 1, 2, 2$ ;
$1, 1, 1, 1, 2, 4$ ;
$1, 1, 1, 1, 2, 2, 2$ ;
$1, 1, 1, 1, 3, 3$ ;
$1, 1, 2, 6$ ;
$1, 1, 2, 2, 4$ ;
$1, 1, 2, 2, 2, 2$ ;
$1, 1, 4, 4$ ;
$1, 3, 6$ ;
$1, 3, 3, 3$ ;
$2, 8$ ;
$2, 2, 6$ ;
$2, 2, 2, 4$ ;
$2, 2, 2, 2, 2$ ;
$2, 4, 4$ ;
$5, 5$ .

So the answer is $26$ .

infO(1)Cup 2025 Day 2 - Mirror | Divisors