NEW

1. Matrix Expo                                                         2. Inclusion - Exclusion
struct MAT {                                                              int RECURSE(ll arr[],ll i,ll j,int num,int numOFele,ll n) {
    ll v[7][7];                                                               // i        : সর্বশেষ সিলেক্টেড এলিমেন্টের ইন্ডেক্স
    int row, col;                                                             // j        : এখন পর্যন্ত যা নেওয়া হয়েছে তাদের lcm
};                                                                            // num      : এখন পর্যন্ত যতোগুলা সিলেক্টেড হইছে
MAT MULTIPLY(MAT A, MAT B) {                                                  // numOFele : মোট এলিমেন্ট সংখ্যা
    MAT ret;                                                                  // n        : লাস্ট নাম্বার রেঞ্জ এর (১ থেকে ১০০)
    ret.row = A.row, ret.col = B.col;                                         if (i == numOFele)
    for (int i = 0; i < ret.row; i++) {											  return 0;
        for (int j = 0; j < ret.col; j++) {                                   int x, y;
            ll sum = 0;                                                       for (x = i; x < numOFele; x++) {
            for (int k = 0; k < A.col; k++) {                                     y = LCM(arr[x], j);
                sum += (A.v[i][k] % MOD * B.v[k][j] % MOD) % MOD;                 if ((num + 1) & 1)
            }																	      ans += (n / y);
            ret.v[i][j] = sum;                                                    else
        }                                                                             ans -= (n / y);
    }                                                                             RECURSE(arr, x + 1, y, num + 1, numOFele, n);
    return ret;                                                               }
}                                                                          }
MAT POWER(MAT mat, ll p) {                                                 // Call : RECURSE(arr, 0, 1, 0, m, n)
    if (p == 1)                                                            // m    : number of element in the set
        return mat;                                                        // n    : range (1000 etc)
    if (p & 1)
        return MULTIPLY(mat, POWER(mat, p-1));
    else
    {
        MAT ret = POWER(mat, p >> 1);
        return MULTIPLY(ret, ret);
    }
}
// call mat = POWER(mat, n - k)