You are given N. Find number of pairs of integers x, y such that

1 <= x < y <= N and sumOfDigits(x) > sumOfDigits(y)

Constraints:

N <= 10^100 and is given as a string.

Output answer modulo 1e9+7

I don't remember the sign of inequality properly, it might be sumOfDigits(x) < sumOfDigits(y). I read about digit DP to solve this but I cannot find any approach.

How to solve this?

keep two tight high (one for x, one for y).

dp states would be : index,thigh1,thigh2,sumx,sumy,flag.

sumx represents sum of digits of x and sumy represents sum of digits of y.

flag is a boolean variable which tells whether at the first place of distinction between digits of x and y , digit of x was smaller or not.