API tools faq
paste
Guest User

Untitled

a guest
Nov 16th, 2018
92
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.43 KB | None | 0 0
raw download clone embed print report
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<set>
  6. #include<map>
  7. #include<functional>
  8. #include<string>
  9. #include<cstring>
  10. #include<cstdlib>
  11. #include<queue>
  12. #include<utility>
  13. #include<fstream>
  14. #include<sstream>
  15. #include<cmath>
  16. #include<stack>
  17. #include<cstdio>
  18. #include <ctime>
  19. #include<cassert>
  20.  
  21. using namespace std;
  22.  
  23. #define MEM(a,b) memset(a,(b),sizeof(a))
  24. #define FOR(i, a, b) for(i=(a);i<=(b);i++)
  25. #define FORR(i, a, b) for(i=(a);i>=(b);i--)
  26. #define S(n) scanf("%d", &n)
  27. #define P(k) printf("%d\n", k)
  28. #define Pl(k) printf("%lld\n", k)
  29. #define pb push_back
  30. #define mp make_pair
  31. #define ll long long
  32. #define VI vector<int>
  33. #define PII pair<int, int>
  34. #define ft first
  35. #define sd second
  36. #define inf (1<<30)
  37. #define PNL primntf("\n")
  38. #define SP system("pause")
  39. #define MOD 1000000007
  40. #define PII pair<int, int>
  41. #define HAHA printf("HAHA\n")
  42.  
  43. int blo[17][2];
  44. pair<int, int> obs[17];
  45. int ax, ay, bx, by, x, y, k, tail, a, b;
  46. ll c[2000][2000];
  47. bool occ[505];
  48. ll dp[505];
  49.  
  50. ll C(int n, int m){
  51. if(n==0){
  52. if(m==0) return 1;
  53. else return 0;
  54. }
  55. if(m==0) return 1;
  56. assert(n<=2000 && m<=2000);
  57. if(c[n][m]!=-1) return c[n][m];
  58. c[n][m] = ( C(n-1, m) + C(n-1, m-1) ) % MOD;
  59. return c[n][m];
  60. }
  61.  
  62. ll DP(int n){
  63. if(n<0) return 0;
  64. assert(n<505);
  65. if(dp[n]!= -1) return dp[n];
  66. dp[n] = (DP(n-a) + DP(n-b)) % MOD;
  67. return dp[n];
  68. }
  69.  
  70. bool pappu(int p, int i, int z){
  71. if(p==0){
  72. assert(0<=i && i<17 && (z==0 || z==1));
  73. if(blo[i][z] == 0) return 1;
  74. else return 0;
  75. }
  76. else if(p>0){
  77. assert(0<=i && i<17 && (z==0 || z==1));
  78. if(blo[i][z]>=0 && blo[i][z]<=p) return 1;
  79. else return 0;
  80. }
  81. else{
  82. assert(0<=i && i<17 && (z==0 || z==1));
  83. if(blo[i][z]<=0 && blo[i][z]>=p) return 1;
  84. else return 0;
  85. }
  86. }
  87.  
  88. int triv(int cx, int cy){
  89. int m;
  90. int i;
  91. if(cx==0){
  92. if(x!=0) return 0;
  93. if(y%(abs(cy))!=0) return 0;
  94. if(y/cy < 0) return 0;
  95. m = y / cy;
  96. FOR(i, 0, k-1){
  97. if(blo[i][0]==0 && blo[i][1]%(abs(cy))==0 && blo[i][1]/cy >= 0 && blo[i][1]/cy <= m) return 0;
  98. }
  99. return 1;
  100. }
  101. else if(cy==0){
  102. if(y!=0) return 0;
  103. if(x%(abs(cx))!=0) return 0;
  104. if(x/cx < 0) return 0;
  105. m = x / cx;
  106. FOR(i, 0, k-1){
  107. if(blo[i][1]==0 && blo[i][0]%(abs(cx))==0 && blo[i][0]/cx >= 0 && blo[i][0]/cx <= m) return 0;
  108. }
  109. return 1;
  110. }
  111. else{
  112. if(x%(abs(cx))!=0) return 0;
  113. if(y%(abs(cy))!=0) return 0;
  114. if(x/cx < 0) return 0;
  115. if(y/cy < 0) return 0;
  116. m = x / cx;
  117. int n = y / cy;
  118. FOR(i, 0, k-1){
  119. if(blo[i][0]%(abs(cx))==0 && blo[i][1]%(abs(cy))==0 && blo[i][0]/cx >= 0 && blo[i][0]/cx <= m && blo[i][1]/cy >= 0 && blo[i][1]/cy <= n) return 0;
  120. }
  121. return 1;
  122. }
  123. return 0;
  124. }
  125.  
  126. int main(){
  127. int i, j, l, n, m, t;
  128.  
  129. FOR(i, 0, 1999) FOR(j, 0, 1999) c[i][j] = -1;
  130. c[0][0] = 1;
  131. FOR(j, 1, 1999) c[0][j] = 0;
  132. FOR(i, 1, 1999) c[i][0] = 1;
  133.  
  134. //srand ( time(NULL) );
  135. // t = 1;
  136. // x = -rand()%500;
  137. // y = rand()%500;
  138. // ax = rand()%500;
  139. // ay = -rand()%500;
  140. // bx = rand()%500;
  141. // by = -rand()%500;
  142. // k = 15;
  143. // FOR(i, 0, 14){
  144. // blo[i][0] = rand()%500;
  145. // blo[i][1] = rand()%500;
  146. // }
  147.  
  148. S(t);
  149. while(t--){
  150. S(x); S(y); S(k);
  151. S(ax); S(ay); S(bx); S(by);
  152. FOR(i, 0, k-1){ S(blo[i][0]); S(blo[i][1]); }
  153.  
  154. if(ax == 0 && ay == 0 && bx == 0 && by==0){ printf("0\n"); continue; }
  155. if(ax == 0 && ay == 0){ printf("%d\n", triv(bx, by)); continue; }
  156. if(bx == 0 && by == 0){ printf("%d\n", triv(ax, ay)); continue; }
  157.  
  158. // now both vectors are non zero
  159.  
  160. if(ax*by != ay*bx){
  161.  
  162. //HAHA;
  163.  
  164. if((x*by-y*bx)%(abs(ax*by-ay*bx)) != 0){ printf("0\n"); continue; }
  165. if((ax*y-ay*x)%(abs(ax*by-ay*bx)) != 0){ printf("0\n"); continue; }
  166. if((x*by-y*bx)/(ax*by-ay*bx) < 0){ printf("0\n"); continue; }
  167. if((ax*y-ay*x)/(ax*by-ay*bx) < 0){ printf("0\n"); continue; }
  168. a = (x*by-y*bx)/(ax*by-ay*bx);
  169. b = (ax*y-ay*x)/(ax*by-ay*bx);
  170. tail = 0;
  171. FOR(i, 0, k-1){
  172. if((blo[i][0]*by-blo[i][1]*bx)%(abs(ax*by-ay*bx)) == 0 &&
  173. (ax*blo[i][1]-ay*blo[i][0])%(abs(ax*by-ay*bx)) == 0 &&
  174. (blo[i][0]*by-blo[i][1]*bx)/(ax*by-ay*bx) >= 0 && (blo[i][0]*by-blo[i][1]*bx)/(ax*by-ay*bx) <= a &&
  175. (ax*blo[i][1]-ay*blo[i][0])/(ax*by-ay*bx) <= b &&
  176. (ax*blo[i][1]-ay*blo[i][0])/(ax*by-ay*bx) >= 0){ obs[tail].ft = (blo[i][0]*by-blo[i][1]*bx)/(ax*by-ay*bx); obs[tail++].sd = (ax*blo[i][1]-ay*blo[i][0])/(ax*by-ay*bx); }
  177. }
  178.  
  179. sort(obs, obs + tail);
  180. tail--;
  181. int i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i13, i14, i15;
  182.  
  183. ll ans = 0;
  184. //P(a); P(b);
  185. ans += C(a+b, b);
  186.  
  187. //Pl(ans);
  188.  
  189. ll temp = 0;
  190. FOR(i, 0, tail){
  191. int c = obs[i].ft;
  192. int d = obs[i].sd;
  193. //P(c); P(d);
  194. temp = (temp + C(c+d, d)*C(a-c+b-d, a-c)) % MOD;
  195. }
  196. ans -= temp;
  197. while(ans<0) ans += MOD;
  198.  
  199. temp = 0;
  200. FOR(i, 0, tail) FOR(j, i+1, tail){
  201. int a1 = obs[i].ft; int b1 = obs[i].sd;
  202. int a2 = obs[j].ft; int b2 = obs[j].sd;
  203. if(b1>b2) continue;
  204. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a-a2+b-b2, a-a2)) % MOD;
  205. }
  206. ans = (ans + temp) % MOD;
  207.  
  208. temp = 0;
  209. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail){
  210. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  211. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  212. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  213. if(b1>b2 || b2>b3) continue;
  214. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a-a3+b-b3, a-a3)) % MOD;
  215. }
  216. ans -= temp;
  217. while(ans<0) ans += MOD;
  218.  
  219. temp = 0;
  220. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail){
  221. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  222. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  223. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  224. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  225. if(b1>b2 || b2>b3 || b3>b4) continue;
  226. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a-a4+b-b4, a-a4)) % MOD;
  227. }
  228. ans += temp;
  229. while(ans>=MOD) ans -= MOD;
  230.  
  231. temp = 0;
  232. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail){
  233. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  234. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  235. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  236. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  237. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  238. if(b1>b2 || b2>b3 || b3>b4 || b4>b5) continue;
  239. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a-a5+b-b5, a-a5)) % MOD;
  240. }
  241. ans -= temp;
  242. while(ans<0) ans += MOD;
  243.  
  244. temp = 0;
  245. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail){
  246. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  247. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  248. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  249. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  250. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  251. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  252. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6) continue;
  253. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a-a6+b-b6, a-a6)) % MOD;
  254. }
  255. ans += temp;
  256. while(ans>=MOD) ans -= MOD;
  257.  
  258. temp = 0;
  259. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail){
  260. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  261. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  262. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  263. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  264. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  265. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  266. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  267. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7) continue;
  268. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a-a7+b-b7, a-a7)) % MOD;
  269. }
  270. ans -= temp;
  271. while(ans<0) ans += MOD;
  272.  
  273. temp = 0;
  274. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail){
  275. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  276. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  277. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  278. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  279. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  280. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  281. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  282. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  283. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8) continue;
  284. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a-a8+b-b8, a-a8)) % MOD;
  285. }
  286. ans += temp;
  287. while(ans>=MOD) ans -= MOD;
  288.  
  289. temp = 0;
  290. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail) FOR(i9, i8+1, tail){
  291. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  292. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  293. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  294. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  295. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  296. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  297. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  298. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  299. int a9 = obs[i9].ft; int b9 = obs[i9].sd;
  300. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8 || b8>b9) continue;
  301. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a9-a8+b9-b8, a9-a8)*C(a-a9+b-b9, a-a9)) % MOD;
  302. }
  303. ans -= temp;
  304. while(ans<0) ans += MOD;
  305.  
  306. temp = 0;
  307. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail) FOR(i9, i8+1, tail) FOR(i10, i9+1, tail){
  308. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  309. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  310. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  311. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  312. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  313. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  314. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  315. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  316. int a9 = obs[i9].ft; int b9 = obs[i9].sd;
  317. int a10 = obs[i10].ft; int b10 = obs[i10].sd;
  318. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8 || b8>b9 || b9>b10) continue;
  319. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a9-a8+b9-b8, a9-a8)*C(a10-a9+b10-b9, a10-a9)*C(a-a10+b-b10, a-a10)) % MOD;
  320. }
  321. ans += temp;
  322. while(ans>=MOD) ans -= MOD;
  323.  
  324. temp = 0;
  325. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail) FOR(i9, i8+1, tail) FOR(i10, i9+1, tail) FOR(i11, i10+1, tail){
  326. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  327. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  328. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  329. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  330. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  331. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  332. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  333. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  334. int a9 = obs[i9].ft; int b9 = obs[i9].sd;
  335. int a10 = obs[i10].ft; int b10 = obs[i10].sd;
  336. int a11 = obs[i11].ft; int b11 = obs[i11].sd;
  337. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8 || b8>b9 || b9>b10 || b10>b11) continue;
  338. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a9-a8+b9-b8, a9-a8)*C(a10-a9+b10-b9, a10-a9)*C(a11-a10+b11-b10, a11-a10)*C(a-a11+b-b11, a-a11)) % MOD;
  339. }
  340. ans -= temp;
  341. while(ans<0) ans += MOD;
  342.  
  343. temp = 0;
  344. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail) FOR(i9, i8+1, tail) FOR(i10, i9+1, tail) FOR(i11, i10+1, tail) FOR(i12, i11+1, tail){
  345. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  346. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  347. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  348. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  349. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  350. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  351. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  352. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  353. int a9 = obs[i9].ft; int b9 = obs[i9].sd;
  354. int a10 = obs[i10].ft; int b10 = obs[i10].sd;
  355. int a11 = obs[i11].ft; int b11 = obs[i11].sd;
  356. int a12 = obs[i12].ft; int b12 = obs[i12].sd;
  357. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8 || b8>b9 || b9>b10 || b10>b11 || b11>b12) continue;
  358. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a9-a8+b9-b8, a9-a8)*C(a10-a9+b10-b9, a10-a9)*C(a11-a10+b11-b10, a11-a10)*C(a12-a11+b12-b11, a12-a11)*C(a-a12+b-b12, a-a12)) % MOD;
  359. }
  360. ans += temp;
  361. while(ans>=MOD) ans -= MOD;
  362.  
  363. temp = 0;
  364. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail) FOR(i9, i8+1, tail) FOR(i10, i9+1, tail) FOR(i11, i10+1, tail) FOR(i12, i11+1, tail) FOR(i13, i12+1, tail){
  365. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  366. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  367. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  368. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  369. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  370. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  371. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  372. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  373. int a9 = obs[i9].ft; int b9 = obs[i9].sd;
  374. int a10 = obs[i10].ft; int b10 = obs[i10].sd;
  375. int a11 = obs[i11].ft; int b11 = obs[i11].sd;
  376. int a12 = obs[i12].ft; int b12 = obs[i12].sd;
  377. int a13 = obs[i13].ft; int b13 = obs[i13].sd;
  378. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8 || b8>b9 || b9>b10 || b10>b11 || b11>b12 || b12>b13) continue;
  379. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a9-a8+b9-b8, a9-a8)*C(a10-a9+b10-b9, a10-a9)*C(a11-a10+b11-b10, a11-a10)*C(a12-a11+b12-b11, a12-a11)*C(a13-a12+b12-b11, a13-a12)*C(a-a13+b-b13, a-a13)) % MOD;
  380. }
  381. ans -= temp;
  382. while(ans<0) ans += MOD;
  383.  
  384. temp = 0;
  385. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail) FOR(i9, i8+1, tail) FOR(i10, i9+1, tail) FOR(i11, i10+1, tail) FOR(i12, i11+1, tail) FOR(i13, i12+1, tail) FOR(i14, i13+1, tail){
  386. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  387. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  388. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  389. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  390. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  391. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  392. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  393. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  394. int a9 = obs[i9].ft; int b9 = obs[i9].sd;
  395. int a10 = obs[i10].ft; int b10 = obs[i10].sd;
  396. int a11 = obs[i11].ft; int b11 = obs[i11].sd;
  397. int a12 = obs[i12].ft; int b12 = obs[i12].sd;
  398. int a13 = obs[i13].ft; int b13 = obs[i13].sd;
  399. int a14 = obs[i14].ft; int b14 = obs[i14].sd;
  400. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8 || b8>b9 || b9>b10 || b10>b11 || b11>b12 || b12>b13 || b13>b14) continue;
  401. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a9-a8+b9-b8, a9-a8)*C(a10-a9+b10-b9, a10-a9)*C(a11-a10+b11-b10, a11-a10)*C(a12-a11+b12-b11, a12-a11)*C(a13-a12+b12-b11, a13-a12)*C(a14-a13+b14-b13, a14-a13)*C(a-a14+b-b14, a-a14)) % MOD;
  402. }
  403. ans += temp;
  404. while(ans>=MOD) ans -= MOD;
  405.  
  406. temp = 0;
  407. FOR(i1, 0, tail) FOR(i2, i1+1, tail) FOR(i3, i2 + 1, tail) FOR(i4, i3+1, tail) FOR(i5, i4+1, tail) FOR(i6, i5+1, tail) FOR(i7, i6+1, tail) FOR(i8, i7+1, tail) FOR(i9, i8+1, tail) FOR(i10, i9+1, tail) FOR(i11, i10+1, tail) FOR(i12, i11+1, tail) FOR(i13, i12+1, tail) FOR(i14, i13+1, tail) FOR(i15, i14+1, tail){
  408. int a1 = obs[i1].ft; int b1 = obs[i1].sd;
  409. int a2 = obs[i2].ft; int b2 = obs[i2].sd;
  410. int a3 = obs[i3].ft; int b3 = obs[i3].sd;
  411. int a4 = obs[i4].ft; int b4 = obs[i4].sd;
  412. int a5 = obs[i5].ft; int b5 = obs[i5].sd;
  413. int a6 = obs[i6].ft; int b6 = obs[i6].sd;
  414. int a7 = obs[i7].ft; int b7 = obs[i7].sd;
  415. int a8 = obs[i8].ft; int b8 = obs[i8].sd;
  416. int a9 = obs[i9].ft; int b9 = obs[i9].sd;
  417. int a10 = obs[i10].ft; int b10 = obs[i10].sd;
  418. int a11 = obs[i11].ft; int b11 = obs[i11].sd;
  419. int a12 = obs[i12].ft; int b12 = obs[i12].sd;
  420. int a13 = obs[i13].ft; int b13 = obs[i13].sd;
  421. int a14 = obs[i14].ft; int b14 = obs[i14].sd;
  422. int a15 = obs[i15].ft; int b15 = obs[i15].sd;
  423. if(b1>b2 || b2>b3 || b3>b4 || b4>b5 || b5>b6 || b6>b7 || b7>b8 || b8>b9 || b9>b10 || b10>b11 || b11>b12 || b12>b13 || b13>b14 || b14>b15) continue;
  424. temp = (temp + C(a1+b1, a1)*C(a2-a1+b2-b1, a2-a1)*C(a3-a2+b3-b2, a3-a2)*C(a4-a3+b4-b3, b4-b3)*C(a5-a4+b5-b4, a5-a4)*C(a6-a5+b6-b5, b6-b5)*C(a7-a6+b7-b6, a7-a6)*C(a8-a7+b8-b7, a8-a7)*C(a9-a8+b9-b8, a9-a8)*C(a10-a9+b10-b9, a10-a9)*C(a11-a10+b11-b10, a11-a10)*C(a12-a11+b12-b11, a12-a11)*C(a13-a12+b12-b11, a13-a12)*C(a14-a13+b14-b13, a14-a13)*C(a15-a14+b15-b14, a15-a14)*C(a-a15+b-b15, a-a15)) % MOD;
  425. }
  426. ans -= temp;
  427. while(ans<0) ans += MOD;
  428.  
  429. Pl(ans); continue;
  430.  
  431. }
  432.  
  433. // now they are linearly dependent non zero vectors
  434. bool opp = true;
  435. if(ax!=0 && ax*bx>0) opp = false;
  436. if(ay!=0 && ay*by>0) opp = false;
  437.  
  438. if(!opp){
  439. if(x*ay != y*ax){ printf("0\n"); continue; }
  440.  
  441. int z = 0, p;
  442. if(ax!=0){ if(ax*x<0){ printf("0\n"); continue; } a = ax; b = bx; z = 0; p = x; }
  443. else if(ay!=0){ if(ay*y<0){ printf("0\n"); continue; } a = ay; b = by; z = 1; p = y; }
  444.  
  445. // a, b, p
  446.  
  447. FOR(i, 0, 502) occ[i] = false;
  448. FOR(i, 0, k-1){
  449. if(ax*blo[i][1]-ay*blo[i][0] == 0 && pappu(p, i, z)) occ[abs(blo[i][z])] = 1;
  450. }
  451.  
  452. a = abs(a); b = abs(b); p = abs(p);
  453. dp[0] = 1;
  454. FOR(i, 1, 502){ if(occ[i]) dp[i] = 0; else dp[i] = -1; }
  455. ll ans = DP(p);
  456. Pl(ans); continue;
  457.  
  458. }
  459.  
  460. else{
  461. printf("-1\n"); continue;
  462. }
  463.  
  464. }
  465. SP;
  466. return 0;
  467. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!