Description

yy is interested in numbers and yy numbers all of the day, Now yy give us the definition of the HK of a decimal number: if(0 <= x < 10)  HK(x) = x, else HK(bit[1]bit[2]..bit[nBit]) = HK(bit[1] + bit[2] +...+bit[nBit]), such as HK(2) = 2, HK(364) = HK(3 + 6 + 4) = HK(13) = HK(1 + 3) = HK(4) = 4. As you can see is easy to a decimal number X's HK(X),  but now yy want to know the smallest x such in the range of 1 to x (1 and x included, x >= 1)  that there exist n decimal numbers who's HK(x) = m.

Input

There are multi case end with EOF

Each  case has two numbers n, m as described above (0 <= n < 10^10000, 1<= m <= 9)

Output

Every case print like this "Case #cas: k" k is the casenumber, k is the smallest x mod 1000000007. If there is no answer just let k = -1.

Sample Input

1 1

2 2

2 1

Sample Output

Case #1: 1

Case #2: 11

Case #3: 10

Hint

In the second case in the range of [1, 11] Only HK(2) and HK(11) equal 2 . So 11 is the smallest number

In the third case in the range of[1, 10] Only HK(1) and HK(10) equal 1. 10 is the smallest number

题意：如果(0 <= x < 10)  HK(x) = x, 否则 HK(bit[1]bit[2]..bit[nBit]) = HK(bit[1] + bit[2] +...+bit[nBit]), 
　　　例如 HK(2) = 2, HK(364) = HK(3 + 6 + 4) = HK(13) = HK(1 + 3) = HK(4) = 4.
　　　给定n和m，就是求第n个和HK（m）的数组下标。
题解：打表发现HK数组是123456789 123456789 123456789.............
　　　得出递归公式 ans=(n-1)*9+m;
　　　注意n高精度取余，用公式取余一下就行了。
　　　注意n=0的时候即存在第0个HK（m）的最小的数组下标，即ans的最小值也就是x最小值1。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <stdlib.h>

#define mod 1000000007

using namespace std;

typedef long long ll;

char c[];

int main()

{

    ll i,n,m,cas=;

    while(scanf("%s",c)!=EOF)

    {

        getchar();

        scanf("%lld",&m);

        int len=strlen(c);

        n=c[]-'';

        if(n==)

        {

            printf("Case #%lld: 1\n",cas++);

            continue;

        }

        for(i=;i<len;i++)

        n=(n*+c[i]-'')%mod;

        ll ans=(*n-+m+mod)%mod;

        printf("Case #%lld: %lld\n",cas++,ans);  //注意cas是long long 要用%lld

    }

    return ;

}