1 #include <iostream>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <stack>
 5 #include <map>
 6 using namespace std;
 7 typedef long long ll;
 8 const ll maxn = 1e5 + 5;
 9 ll dp[51][1005][460];
10 bool vis[1005];
11 ll num[1005];
12 const ll mod=1000009;
13 int main() {
14     ll n, sum, last, w, x, s, i, j, t,k, ss,ans = 0, cnt;
15     while (cin >> n >> s >> x) {
16         cnt = 1;
17         map<ll,ll>mp;
18         memset(vis, false, sizeof(vis));
19         memset(dp, 0, sizeof(dp));
20         for (i = 0; i < 1000; i++)
21             if (i % x == 0)
22                mp[i]=cnt, num[cnt++] = i, vis[i] = true;
23         for(i=1;i<cnt;i++)
24         {
25              w=num[i]%10;
26              t=(num[i]/10)%10;
27              ss=num[i]/100;
28              sum=ss*100+t*10+w;
29             dp[3][i][ss+t+w]=1;
30         }
31         for(i=3;i<=n-1;i++)
32         {
33             for(j=1;j<cnt;j++)
34             {
35                 sum=num[j]%100;
36                 for(t=0;t<10;t++)
37                 {
38                     if(vis[sum*10+t])
39                     {
40                         w=mp[sum*10+t];
41                         for(k=0;k<=450;k++)
42                         {
43                             dp[i+1][w][k+t]=(dp[i][j][k]+dp[i+1][w][k+t])%mod;
44 
45                         }
46                     }
47                 }
48             }
49         }
50         sum=0;
51         for(i=1;i<cnt;i++)
52             sum=(dp[n][i][s]+sum)%mod;
53        cout<<sum<<endl;
54 
55     }
56     return 0;
57 }