Given two positive integer n and n. The task is to find the number of arrays of size n that can be formed such that :

Each element is in range [1, m]

All adjacent element are such that one of them divide the another i.e element Ai divides Ai + 1 or Ai + 1 divides Ai + 2.

Examples:

Input : n = 3, m = 3.

Output : 17

{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1},

{1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},

{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},

{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1},

{3,3,3} are possible arrays.

Input : n = 1, m = 10.

Output : 10

can any one help me in this interesting dp problem?