果然是codeforces的题，太良心了，模数1e9+7,1e9+9甚至rand()全都卡，必须自然溢出才能过