### Problem Statement

A square-free number is an integer that is not divisible by the square of any integer except 1. A set containing only square-free numbers is called a square-free set. The product of such a set is the product of all its elements. If the product of a square-free set is a square-free number itself, that set is called a perfect set.

You are given two ints N and K. Determine the number of perfect square-free sets that contain between 1 and K elements, inclusive, where each element is between 2 and N, inclusive. Return this number modulo 1,000,000,007.

### Definition

 Class: SquareFreeSets Method: countPerfect Parameters: int, int Returns: int Method signature: int countPerfect(int N, int K) (be sure your method is public)

### Constraints

-N will be between 2 and 500, inclusive.
-K will be between 1 and 500, inclusive.

### Examples

0)

 `5` `1`
`Returns: 3`
 The possible sets are: {2}, {3}, {5}.
1)

 `5` `2`
`Returns: 6`
 Here, {2,3}, {2,5} and {3,5} are also possible.
2)

 `5` `3`
`Returns: 7`
 The set {2,3,5} is added to the previous ones.
3)

 `6` `3`
`Returns: 9`
 Here, the sets are: {2}, {3}, {5}, {6}, {2,3}, {2,5}, {3,5}, {5,6}, {2,3,5}.
4)

 `28` `41`
`Returns: 1599`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10386

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13748&pm=10386

gojira_tc

#### Testers:

PabloGilberto , ivan_metelsky , Vasyl[alphacom]

#### Problem categories:

Dynamic Programming, Math