When counting paths modulo , take the modulo after every addition to prevent overflow. Do not do this: compute the full sum first, then take modulo. That can overflow. Do this: dp[v] = ((dp[v] + dp[u_1]) % M + dp[u_2]) % M + ... This keeps intermediate values small and avoids integer overflow.
In practice, write dp[v] = (dp[v] + dp[u]) % M inside the loop that processes edges.