Guest User

C

a guest
Apr 25th, 2013
5,131
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #define _SECURE_SCL 0
  3. #pragma comment(linker, "/STACK:200000000")
  4.  
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <cassert>
  8. #include <cctype>
  9. #include <complex>
  10. #include <ctime>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <deque>
  15. #include <functional>
  16. #include <fstream>
  17. #include <iostream>
  18. #include <map>
  19. #include <memory.h>
  20. #include <numeric>
  21. #include <iomanip>
  22. #include <queue>
  23. #include <set>
  24. #include <stack>
  25. #include <list>
  26. #include <string>
  27. #include <sstream>
  28. #include <vector>
  29. #include <utility>
  30. #include <cmath>
  31. using namespace std;
  32.  
  33. #define pb push_back
  34. #define mp make_pair
  35. #define mset(mas,val) memset(mas,val,sizeof(mas))
  36. #define sz(a) (int)(a).size()
  37. #define all(a) (a).begin(), (a).end()
  38. #define rall(a) (a).rbegin(), (a).rend()
  39.  
  40. #define forn(i,n) for (int i=0; i<int(n); ++i)
  41. #define fornd(i,n) for (int i=int(n)-1; i>=0; --i)
  42. #define forab(i,a,b) for (int i=int(a); i<int(b); ++i)
  43.  
  44. typedef long long ll;
  45. typedef long double ld;
  46. typedef unsigned long long ull;
  47.    
  48. const int INF = (int) 1e9;
  49. const long long INF64 = (long long) 1e18;
  50. long double eps = 1e-6;
  51. const long double pi = 3.14159265358979323846;
  52.  
  53. const int N = 1e6 + 100;
  54. long long fact[N], modulo = INF + 7;
  55. int n, a, b;
  56. bool read()
  57. {
  58.     if (!(cin >> a >> b >> n))
  59.         return false;
  60.     assert(a >= 1 && a <= 9);
  61.     assert(b >= a + 1 && b <= 9);
  62.     assert(n >= 1 && n <= (int)1e6);
  63.     return true;
  64. }
  65. long long binpow(long long val, long long deg, long long mod) {
  66.     if (!deg) return 1 % mod;
  67.     if (deg & 1) return binpow(val, deg - 1, mod) * val % mod;
  68.     long long res = binpow(val ,deg >> 1, mod);
  69.     return (res*res) % mod;
  70. }
  71. bool check(long long val, int a, int b) {
  72.     while (val > 0) {
  73.         if (val % 10 == a || val % 10 == b) {
  74.             val /= 10;
  75.         } else return false;
  76.     }
  77.     return true;
  78. }
  79. void initfact() {
  80.     fact[0] = 1;
  81.     for(int i = 1; i < N; i++) {
  82.         fact[i] = (fact[i-1] * i);
  83.         fact[i] %= modulo;
  84.     }
  85. }
  86. long long getC(int n, int i) {
  87.     long long res = fact[n];
  88.     long long div = fact[n-i] * fact[i];
  89.     div %= modulo;  div = binpow(div, modulo - 2, modulo);
  90.     return (res * div) % modulo;
  91. }
  92. void solve()
  93. {
  94.     long long ans = 0;
  95.     for(int i = 0; i <= n; i++) {
  96.         long long expsum = a * i + b*(n-i);
  97.         if (check(expsum, a, b)) {
  98.             ans += getC(n, i);
  99.             ans %= modulo;
  100.         }
  101.     }
  102.     cout << ans << endl;
  103. }
  104.  
  105. int main(){
  106. #ifdef gridnevvvit
  107.     freopen("input.txt","rt",stdin);
  108.     freopen("output.txt","wt",stdout);
  109. #endif
  110.     initfact();
  111.     assert(read());
  112.     solve();
  113.     return 0;
  114. }
RAW Paste Data