//f(l) + … + f(r)を求めることを考えると、f(l)とf(r)は固定したくなって(f(l) = aとおく)、
//f(l) = f(r) (1区間に収まる), f(l) + 1 = f(r) (区間を跨ぐ), f(l) + 2 ≦ f(r) (区間を飛び越える)
//を考えるまでは定石っぽい感じがする。f(l) + 2 ≦ f(r)は尺取り、f(l) = f(r)は約数列挙、
//f(l) + 1 = f(r)はf(l)の大きさで場合分け。f(l)が大きい時は自明全探索。小さい時は、
//拡張ユーグリッドに見えるけど実はいらない。
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2) return (a * powmod(a, n - 1, mod)) % mod;
	return powmod((a * a) % mod, n / 2, mod);
}

int mod = 1000000007;
int s;
int p10[10];

int digit(int x) {
	int ret = 0;
	while (x > 0) {
		x /= 10;
		ret++;
	}
	return ret;
}

int calc0(int s) {
	int i;
	vector<int> yaku;
	
	for (i = 1; i * i <= s; i++) {
		if (s % i == 0) {
			yaku.push_back(i);
			if (i != s / i) yaku.push_back(s / i);
		}
	}
	
	int ret = 0;
	for (i = 0; i < yaku.size(); i++) {
		int a = yaku[i];
		if (a >= 8 || p10[a - 1] * 9 >= s / a) {
			ret += powmod(10, a - 1, mod) * 9 % mod + mod - s / a + 1;
			ret %= mod;
		}
	}
	return ret;
}

int calc2(int s) {
	int l, r;
	int sumD = 0;
	int ret = 0;
	
	r = 1;
	for (l = 1; l < 1000000; l++) {
		for (; sumD < s; r++) {
			sumD += digit(r);
		}
		if (sumD == s && digit(l) + 2 <= digit(r - 1)) {
			ret++;
		}
		sumD -= digit(l);
	}
	return ret;
}

int calc1(int s) {
	int a, x, y;
	int ret = 0;
	
	for (a = 1; a <= 1000000; a++) {
		int lowT = ((s + 1) + a) / (a + 1);
		if (a <= 7) { lowT = max(lowT, ((s - 9 * p10[a]) + (a - 1)) / a); }
		int highT = (s - 1) / a;
		if (a <= 8) { highT = min(highT, (s + 9 * p10[a - 1]) / (a + 1)); }
		
		int cntT = max(highT - lowT + 1, 0LL);
		ret += cntT;
		ret %= mod;
	}
	
	for (x = 1; x <= 100; x++) {
		for (y = 1; y <= 100; y++) {
			if (s >= y && (s - y) % (x + y) == 0) {
				int a = (s - y) / (x + y);
				if (a > 1000000) { ret++; }
			}
		}
	}
	return ret;
}

signed main() {
	int i;
	
	p10[0] = 1;
	for (i = 1; i < 10; i++) p10[i] = 10 * p10[i - 1];
	
	cin >> s;
	cout << (calc0(s) + calc1(s) + calc2(s)) % mod << endl;
	return 0;
}
### Prompt

In Cpp, your task is to solve the following problem:

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.

Examples

Input

1


Output

9


Input

2


Output

98


Input

123


Output

460191684


Input

36018


Output

966522825


Input

1000


Output

184984484

### Response

```cpp
//f(l) + … + f(r)を求めることを考えると、f(l)とf(r)は固定したくなって(f(l) = aとおく)、
//f(l) = f(r) (1区間に収まる), f(l) + 1 = f(r) (区間を跨ぐ), f(l) + 2 ≦ f(r) (区間を飛び越える)
//を考えるまでは定石っぽい感じがする。f(l) + 2 ≦ f(r)は尺取り、f(l) = f(r)は約数列挙、
//f(l) + 1 = f(r)はf(l)の大きさで場合分け。f(l)が大きい時は自明全探索。小さい時は、
//拡張ユーグリッドに見えるけど実はいらない。
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2) return (a * powmod(a, n - 1, mod)) % mod;
	return powmod((a * a) % mod, n / 2, mod);
}

int mod = 1000000007;
int s;
int p10[10];

int digit(int x) {
	int ret = 0;
	while (x > 0) {
		x /= 10;
		ret++;
	}
	return ret;
}

int calc0(int s) {
	int i;
	vector<int> yaku;
	
	for (i = 1; i * i <= s; i++) {
		if (s % i == 0) {
			yaku.push_back(i);
			if (i != s / i) yaku.push_back(s / i);
		}
	}
	
	int ret = 0;
	for (i = 0; i < yaku.size(); i++) {
		int a = yaku[i];
		if (a >= 8 || p10[a - 1] * 9 >= s / a) {
			ret += powmod(10, a - 1, mod) * 9 % mod + mod - s / a + 1;
			ret %= mod;
		}
	}
	return ret;
}

int calc2(int s) {
	int l, r;
	int sumD = 0;
	int ret = 0;
	
	r = 1;
	for (l = 1; l < 1000000; l++) {
		for (; sumD < s; r++) {
			sumD += digit(r);
		}
		if (sumD == s && digit(l) + 2 <= digit(r - 1)) {
			ret++;
		}
		sumD -= digit(l);
	}
	return ret;
}

int calc1(int s) {
	int a, x, y;
	int ret = 0;
	
	for (a = 1; a <= 1000000; a++) {
		int lowT = ((s + 1) + a) / (a + 1);
		if (a <= 7) { lowT = max(lowT, ((s - 9 * p10[a]) + (a - 1)) / a); }
		int highT = (s - 1) / a;
		if (a <= 8) { highT = min(highT, (s + 9 * p10[a - 1]) / (a + 1)); }
		
		int cntT = max(highT - lowT + 1, 0LL);
		ret += cntT;
		ret %= mod;
	}
	
	for (x = 1; x <= 100; x++) {
		for (y = 1; y <= 100; y++) {
			if (s >= y && (s - y) % (x + y) == 0) {
				int a = (s - y) / (x + y);
				if (a > 1000000) { ret++; }
			}
		}
	}
	return ret;
}

signed main() {
	int i;
	
	p10[0] = 1;
	for (i = 1; i < 10; i++) p10[i] = 10 * p10[i - 1];
	
	cin >> s;
	cout << (calc0(s) + calc1(s) + calc2(s)) % mod << endl;
	return 0;
}
```