For a positive integer n, let us define f(n) as the number of digits in base 10.
You are given an integer S.
Count the number of the pairs of positive integers (l, r) (l \leq r) such that f(l) + f(l + 1) + ... + f(r) = S, and find the count modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq S \leq 10^8

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the answer.

-----Sample Input-----
1

-----Sample Output-----
9

There are nine pairs (l, r) that satisfies the condition: (1, 1), (2, 2), ..., (9, 9).

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline

from fractions import gcd
import numpy as np

MOD = 10 ** 9 + 7

S = int(input())

M = 10**4

def type_1(S):
    cnt = 0
    # S 2種の桁数k,k+1からなる。さらにk>=9を仮定する。
    # 項数nとすると、kn < S < (k+1)n となる(k,n)の個数を数える
    # まずk > Mとなるものを数える。このとき1<=n<=Mである。
    n = np.arange(1,M+1)
    k_max = (S-1)//n
    k_min = np.maximum(M+1,S//n)
    cnt += np.maximum(0,k_max - k_min + 1).sum()
    # 次に、9<=k<=Mとなるものを数える
    k = np.arange(9,M+1)
    n_max = (S-1)//k
    n_min = S//(k+1) + 1
    cnt += np.maximum(0,n_max-n_min+1).sum()
    return cnt

type_1(S)

def type_2(S):
    # S 1種の桁数からなる。
    cnt = 0
    div = np.arange(1,M+1,dtype=np.int64)
    div = set(div[S%div==0])
    div |= set(S//x for x in div)
    for d in div:
        n = S//d
        # d桁のものをn個使うようにしたい
        if d < 10:
            total = 9 * 10 ** (d-1)
            cnt += max(0,total-n+1)
        else:
            total = 9 * pow(10,int(d)-1,MOD)
            cnt += total-n+1
    return cnt % MOD

def type_3(S):
    cnt = 0
    # S 2種以上の桁数からなる。9桁の数以下しか使わない。
    # ここは適当にいけそう
    for R in range(1,10):
        for L in range(1,R):
            mid = sum(i*9*10**(i-1) for i in range(L+1,R)) # 途中の桁数の寄与
            rest = S - (L+mid+R)
            if rest < 0:
                continue
            # Lが1+x個、Rが1+y個として
            # Lx + Ry = rest, 0<=x<=x_max, 0<=y<=y_max
            x_max = 9*10**(L-1)-1
            y_max = 9*10**(R-1)-1
            g = gcd(L,R)
            if rest % g != 0:
                continue
            L0 = L//g
            R0 = R//g
            rest //= g
            # x mod R0が一意に決まる
            for x0 in range(R0):
                if (L0*x0-rest)%R0 == 0:
                    break
            y0 = (rest-L0*x0)//R0
            # (x0 + tR, y0-tL)として解がパラメータ表示できる
            # 0 <= x0 + tR <= x_max
            t_min = 0
            t_max = (x_max-x0)//R0
            # y0-tL >= 0
            t_max = min(t_max,y0//L0)
            # y0-tL <= y_max iff y0-y_max <= tL
            t_min = max(t_min,(y0-y_max+L-1)//L0)
            cnt += max(0, t_max - t_min + 1)
    return cnt

answer = (type_1(S) + type_2(S) + type_3(S)) % MOD
print(answer)

#!/usr/bin/env python3
import math
import random

class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_bf(n)
        else:
            return self.is_prime_mr(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any([n % x == 0 for x in self.seed_primes]): return False

    def is_prime_bf(self, n):
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_mr(self, n):
        d = n - 1
        while d % 2 == 0:
            d //= 2

        witnesses = self.get_witnesses(n)
        #witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            t = d
            y = pow(w, t, n)

            while t != n - 1 and y != 1 and y != n - 1:
                y = (y ** 2) % n
                t *= 2

            if y != n - 1 and t % 2 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 38255123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            a, b = b, a
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


def gcd(a, b):
    if a < b:
        a, b = b, a
    while 0 < b:
        a, b = b, a % b
    return a


def powmod(a, x, m):
    y = 1
    while 0 < x:
        if x % 2 == 1:
            y *= a
            y %= m
        x //= 2
        a = a ** 2
        a %= M

    return y

M = 10 ** 9 + 7
prime = Prime()


def solve(s):

    if s == 1:
        return 9

    ans = 0

    n = 1
    c = 9
    while n * c < s:
        n += 1
        c *= 10

    ans += s // n

    for log_r in range(n - 1, n + 1):
        c_r = 9 * 10 ** (log_r - 1)
        sum_r = log_r * c_r
        for log_l in range(1, log_r):
            mid_f = 0
            for i in range(log_l + 1, log_r):
                mid_f += i * 9 * 10 ** (i - 1)
            if s <= mid_f:
                continue
            res = s - mid_f
            c_l = 9 * 10 ** (log_l - 1)
            if log_l * c_l + sum_r < res:
                continue
            g = gcd(log_r, log_l)
            if res % g != 0:
                continue
            c_l_max = min(c_l, (res - 1) // log_l)
            while 0 < c_l_max:
                if (res - log_l * c_l_max) % log_r == 0: break
                c_l_max -= 1
            if c_l_max == 0:
                continue
            c_l_min = 1
            if sum_r < res:
                c_l_min = (res - sum_r + log_l - 1) // log_l
            div = log_r // g
            ans += (c_l_max - c_l_min + div) // div


    factors = prime.find_factors(s)
    num_prime_factors = len(factors)
    prime_factors = []
    count_limit = []
    count = [0] * num_prime_factors
    for k in list(factors.keys()):
        prime_factors.append(k)
        count_limit.append(factors[k])

    loop = True
    while loop:
        p = 1
        for i, f in enumerate(prime_factors):
            p *= f ** count[i]
        if n <= p:
            ans += 9 * powmod(10, p - 1, M)
            ans += M - s // p
            ans %= M

        count[0] += 1
        for i, limit in enumerate(count_limit):
            if limit < count[i]:
                if i == num_prime_factors - 1:
                    loop = False
                    break
                count[i + 1] += 1
                count[i] = 0

    return ans

def main():

    s = int(input())

    print((solve(s)))


def __starting_point():
    main()


__starting_point()