// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int mod=1e9+7;
int power(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ret;
}
int s,p10[12000111],f[23000111];
int main()
{
	p10[0]=1;for(int i=1;i<12000111;i++)p10[i]=10ll*p10[i-1]%mod;
	get1(s);
	for(int i=1;i<=23000000;i++)f[i]=f[i/10]+1;
	for(int i=1;i<=23000000;i++)f[i]+=f[i-1];
	int r=1,ans=s/8;
	for(int l=1;l<10000000;l++)
	{
		while(r<23000111&&f[r]-f[l-1]<s)r++;
		if(f[r]==f[l-1]+s)ans++;
	}
	for(int i=1;i<=s/8;i++)if(s%i==0)
		ans=(ans+9ll*power(10,s/i-1)-i+mod)%mod;
	printf("%d\n",ans);
	return 0;
}
### Prompt

Please create a solution in Cpp to 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
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int mod=1e9+7;
int power(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ret;
}
int s,p10[12000111],f[23000111];
int main()
{
	p10[0]=1;for(int i=1;i<12000111;i++)p10[i]=10ll*p10[i-1]%mod;
	get1(s);
	for(int i=1;i<=23000000;i++)f[i]=f[i/10]+1;
	for(int i=1;i<=23000000;i++)f[i]+=f[i-1];
	int r=1,ans=s/8;
	for(int l=1;l<10000000;l++)
	{
		while(r<23000111&&f[r]-f[l-1]<s)r++;
		if(f[r]==f[l-1]+s)ans++;
	}
	for(int i=1;i<=s/8;i++)if(s%i==0)
		ans=(ans+9ll*power(10,s/i-1)-i+mod)%mod;
	printf("%d\n",ans);
	return 0;
}
```