could you describe your solution? my algo O(logn * l^3 * t) has TL(
i try to find solution like this: dp[i, a, l] , i is bit number, a is addition to i-bit, l is lost count

Yes, there is. (L^2)*log(N) solution (0.187 sec). I DP on total amount of coins and amount of extra coins for next denomination (the latter is used to know how much more can I push forward when I advance a digit). The first index always increases by K-1, the second always increases by K, so it's kind of diagonal partial summing up matrix to itself. If you precalculate reachable sums properly, you can perform DP transfer in O(L^2).

Input:
2
100 2 20
1000000000000000000 2 100

Output:
184
967176416