### PROBLEM LINK

### Panel Members

**Problem Setter:** Sergey Nagin

**Problem Tester:** Istvan Nagy

**Editorialist:** Sunny Aggarwal

**Contest Admin:** Praveen Dhinwa

**Russian Translator:** Sergey Nagin

**Mandarin Translator:** Hu Zecong

**Vietnamese Translator:** VNOI Team

**Language Verifier:** Rahul Arora

### DIFFICULTY:

medium

### PREREQUISITES:

Dynamic Programming, Number Theory, Trees

### PROBLEM:

Given a rooted tree T consisting of N nodes and an integer M. We are asked to calculate the number of ways of putting integers from range [1, M] in each node of the tree T such that for any pair of nodes \left(A, B\right) ( where A is parent of node B ) the number assigned to node B is divisible by the number assigned to node A. Since this answer can be very large, Print the answer modulo 10^9 + 7.

### QUICK EXPLANATION

Number of valid configuration (as mentioned in problem statement) for a tree rooted at a node can be computed from the valid configuration of trees rooted at its children nodes i.e number of ways of assigning a particular number say K to a node say V such that the tree rooted at node V has a valid configuration can be calculated from the number of ways of assigning multiples of number K to the children nodes of V such that trees rooted at children nodes also has a valid configuration.

### EXPLANATION

Lets use some notation to make the explanation more understandable. Let us consider that the function F_{\left(V, K\right)} denotes the number of ways of assigning a number K to the node V such that tree rooted at node V has a valid configuration and the function D_{\left(V, K\right)} denotes the number of ways of assigning any multiple of number K to the node V such that tree rooted at node V has a valid configuration.

Therefore,

**How to compute F_{(V, K)} for all K \in [1, M] for any node V ?**

As mentioned above, number of ways of assigning a particular number say K to a node say V such that the tree rooted at node V has a valid configuration can be calculated from the number of ways of assigning multiples of number K to the children nodes of V such that trees rooted at children nodes also has a valid configuration.

For any non leaf node V,

otherwise

Note that the function F for a node V depends upon the children nodes of V.

**How to compute D_{(V, K)} for all K \in [1, M] for any node V ?**

Let us consider that we have already calculated F_{(V, K)} for all K \in [1, M].

Then, For some K \in [1, M]

Note that the function D for a node V depends upon the function F for the same node V and can be computed using following simple procedure.

int D[M+1]; int F[M+1]; for(int i=1; i<=M; i++) { int j = i; while( j<=M ) { // iterating over multiples of i D[i] += F[j]; j += i; } }

Look at the following C++ code for the better understanding of above explanation:

int N, M; int F[N+1][M+1]; int D[N+1][M+1]; void dfs(int u, int p = -1) { bool isleaf = true; for(int i=1; i<adj[u].size(); i++) { if( adj[u][i] != p ) { isleaf = false; dfs(adj[u][i], u); } } if( isleaf ) { // leaf node base case for(int i=1; i<=m; i++) { F[u][i] = 1; } } else { // computing function F as per our recurrence for(int j=1; j<=m; j++) { int v = 1; for(int i=0; i<adj[u].size(); i++) { if(adj[u][i] != p) { v = 1LL * v * D[adj[u][i]][j]; } } F[u][j] = v; } } // computing function D using function F. for(int i=1; i<=m; i++) { int j = i; while( j <= m ) { D[u][i] += F[u][j]; j += i; } } }

### COMPLEXITY

O(NM\log(M)) per test case.

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.

The tester’s solution can be found here.

The editorialist’s solution can be found here.

### SIMILAR PROBLEMS:

Codeforces Testing round 10 - D