void inv(mat &x){ int n = 2, is[2], js[2]; memset(is, 0, sizeof(is)); memset(js, 0, sizeof(js)); for (int k = 0; k < n; k++) { for (int i = k, j; i < n; i++) { for (j = k; j < n && !x.a[i][j]; j++); is[k] = i, js[k] = j; } for (int i = 0; i < n; i++) swap(x.a[k][i],x.a[is[k]][i]); for (int i = 0; i < n; i++) swap(x.a[i][k], x.a[i][js[k]]); if (x.a[k][k]==0){ puts("No Solution"); exit(0) ; } x.a[k][k] = inv(x.a[k][k]); for (int j = 0; j < n; j++) if (j != k) (x.a[k][j] *= x.a[k][k]) %= mod; for (int i = 0; i < n; i++) if (i != k) { int temp = x.a[i][k]; x.a[i][k] = 0; for(int j = 0; j < n; ++j) (x.a[i][j] += mod - x.a[k][j] * temp % mod) %= mod; } } for (int k=n-1; k>=0; k--){ for (int i = 0; i < n; i++) swap(x.a[js[k]][i], x.a[k][i]); for (int i = 0; i < n; i++) swap(x.a[i][is[k]],x.a[i][k]); } }