1#include <algorithm>2#include <cstdio>3#include <cstring>4#include <vector>5#define ll long long6int n, m;7std::vector<int> k, p;8inline int mpow(int x, int k) {9    int ans = 1;10    for (; k; k >>= 1, x = x * x) {11        if (k & 1)12            ans = ans * x;13    }14    return ans;15}16std::vector<int> ans1, ans2;17int cnt1, cnt2;18inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {19    if (l > r) {20        ++cnt;21        ans.push_back(v);22        return;23    }24    for (int i = 1; i <= m; ++i) {25        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));26    }27    return;28}29std::vector<int> cntans1;30int main() {31    scanf("%d%d", &n, &m);32    k.resize(n + 1);33    p.resize(n + 1);34    for (int i = 1; i <= n; ++i) {35        scanf("%d%d", &k[i], &p[i]);36    }37    dfs(ans1, cnt1, 1, n >> 1, 0);38    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);39    std::sort(ans1.begin(), ans1.end());40    int newcnt1 = 1;41    cntans1.push_back(1);42    for (int i = 1; i < cnt1; ++i) {43        if (ans1[i] == ans1[newcnt1 - 1]) {44            ++cntans1[newcnt1 - 1];45        } else {46            ans1[newcnt1++] = ans1[i];47            cntans1.push_back(1);48        }49    }50    cnt1 = newcnt1;51    std::sort(ans2.begin(), ans2.end());52    int las = 0;53    ll ans = 0;54    for (int i = cnt2 - 1; i >= 0; --i) {55        for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)56            ;57        if (las < cnt1 && ans1[las] + ans2[i] == 0)58            ans += cntans1[las];59    }60    printf("%lld\n", ans);61    return 0;62}