← RoseCode

ROSECODE 484

Product of tuple

liuguangxi · Math ·

Let S(p,n) denote the number of n-tuples of positive integers whose product is no larger than p. For example, S(4,2)=8, as there are eight 2-tuples (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (3, 1), (4, 1) meet the condition. You are also given S(6,4)=39, S(10,10)=571, S(100,100)mod1000000007=959337187.

Find S(1012,1012)mod1000000007.
Thanks to baihacker for the idea.

This problem was inspired by Problem 452 at Project Euler (https://projecteuler.net/problem=452)