思路：
  不难得出，对于任意的背包ii和一个背包jj (i≠j)(i≠j)，他们俩对答案的贡献为Cai+ajai+bi+aj+bjCai+bi+aj+bjai+aj，因为形成一种烤串时，所有的菜和肉都要用完，所以总共有ai+bi+aj+bjai+bi+aj+bj个位置，从中挑出ai+ajai+aj个位置来放菜，剩下的就是肉的位置。

  于是，容易推出，对于一组样例来说，最终答案就是∑ni=1∑nj=i+1Cai+ajai+bi+aj+bj∑i=1n∑j=i+1nCai+bi+aj+bjai+aj，但这样是O(n2)O(n2)的。

  可以观察到，1≤ai,bi≤20001≤ai,bi≤2000，他们俩相乘最大的范围只有4×1064×106，可以通过枚举aa和bb来求出所有需要的组合数，可是加和的过程依然是O(n2)O(n2)的。

  假设平面上存在两个点A(x,y)、B(p,q)A(x,y)、B(p,q)，A在B的左下方，那么当A以向右或向上走的方式到达B的方案数就等于Cp−xp−x+q−yCp−x+q−yp−x，于是对于本题的Cai+ajai+bi+aj+bjCai+bi+aj+bjai+aj来说，就等于平面上有两个点A(−aj,−bj)、B(ai,bi)A(−aj,−bj)、B(ai,bi)，A点只向右或向上走到达B点的方案数。

  于是，小小的容斥一下，做一个转化：

  ∑ni=1∑nj=i+1Cai+ajai+bi+aj+bj∑i=1n∑j=i+1nCai+bi+aj+bjai+aj
=[(∑ni=1∑nj=1Cai+ajai+bi+aj+bj)−∑ni=1Cai×2(ai+bi)×2]÷2=[(∑i=1n∑j=1nCai+bi+aj+bjai+aj)−∑i=1nC(ai+bi)×2ai×2]÷2
  其中：∑ni=1Cai×2(ai+bi)×2∑i=1nC(ai+bi)×2ai×2 很好求，主要就是求减号左边的部分，可以通过转化为二维平面上点的问题动态规划出来。

  记dp[i][j]dp[i][j]为平面上(i,j)(i,j)这个点的左方、左下方、下方所有存在的点向右或向上走到达这个点的方案数，转移方程为：
dp[i][j]=dp[i−1][j]+dp[i][j−1]
dp[i][j]=dp[i−1][j]+dp[i][j−1]
  不难看出，∑nj=1Cai+ajai+bi+aj+bj=dp[ai][bi]∑j=1nCai+bi+aj+bjai+aj=dp[ai][bi]，于是就可以将O(n2)O(n2)的复杂度降至O(n)O(n)。