Partitions on Integer Permutations

Let $S_n$ be the set of all permutations of integers from $1$ to $n$. Let $P_1$ and $P_2$ be two partitions defined on $S_n$ as follows.

$P_1$ is the set of all those permutations which have even number of cycles. $P_2$ is the set of all those permutations which have odd number of cycles. The sets $P_1$ and $P_2$ have a lexicographic ordering imposed on them.

Given a permutation $P$

1. Tell which partition it belongs to
2. What is the lexicographic rank($1$ based indexing) of this permutation in that partition. If this rank is $K$, you have to specify the number $K$ mod $M$ where $M = 1000000007 (1e9 + 7)$

Here $N$ can be as large as $10^5$

My approach: Calculate the number of cycles in P using a simple DFS technique on my computer and decide which partition it belongs to. For calculating rank I first calculate its rank in the set $S_n$ Let that rank be $K_1$($1$ based indexing) then the actual rank is coming out to be floor($\frac{K_1+1}{2}$). I am having trouble applying modular arithmetic on this expression. Is there any other way to solve this problem?

Note: By "cycle" I mean when the permutation is represented as a graph, the number of components or disjoint forests formed.

• @AndrásSalamon I have corrected the question – lassaendie Oct 5 '15 at 11:41
{"ft_lang_label":"__label__en","ft_lang_prob":0.90038335,"math_prob":0.9994642,"size":1195,"snap":"2019-26-2019-30","text_gpt3_token_len":319,"char_repetition_ratio":0.12426532,"word_repetition_ratio":0.04784689,"special_character_ratio":0.27782428,"punctuation_ratio":0.064935066,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99999523,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-06-25T11:57:36Z\",\"WARC-Record-ID\":\"<urn:uuid:06759e64-0f56-437b-9927-4a75dc1dd959>\",\"Content-Length\":\"140452\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:20fb4eb9-56bb-4006-84e3-ab893345b704>\",\"WARC-Concurrent-To\":\"<urn:uuid:3ad39d62-1362-4185-a6cf-efd85c9703cc>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://cstheory.stackexchange.com/questions/32704/partitions-on-integer-permutations\",\"WARC-Payload-Digest\":\"sha1:62GCIGNNKBBGGEM3E2HNOW4UWLDWZOQ3\",\"WARC-Block-Digest\":\"sha1:6L7SWKJBV6GPEDG7RFI7T3MPDOTZIL2X\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-26/CC-MAIN-2019-26_segments_1560627999838.23_warc_CC-MAIN-20190625112522-20190625134522-00149.warc.gz\"}"}