DIVSEQ - DIVSEQ


You're given two numbers - N and K  (0 < N, K <= 1000). You have to count the number of sequences of positive integers with length N where every element must be not greater than K and for every two consecutive elements with indices i and i + 1 one of the conditions bellow must be true:

  1. a[i] is divisible by a[i + 1]
  2. a[i + 1] is divisible by a[i]

Input

On the only line you will be given the values of N and K.

Output

Print the number of the sequences described above modulо 1000000009.

Example

Input:
2 4

Output:
12

hide comments
gurugs: 2016-03-03 20:21:29

i am getting all WAs

gurugs: 2016-03-03 20:20:09

someone explain the problem please...especially the meaning "every element not greater than K" and the two conditions ...explain the test case also...thanks in advance

abdou_93: 2016-03-03 14:46:23

elements can be negative or zero
EDIT1:The statement is corrected

Last edit: 2016-03-03 15:36:35

Added by:ivokaragyozov
Date:2016-03-03
Time limit:0.200s-0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:http://www.math.bas.bg/infos/files/2013-05-02-C1.pdf