2lines

#include<bits/stdc++.h>
int main(){printf("6596\n2196\n9671200\n1\n2196");}