Not Palindrome

Sumo was travelling alone at night, suddenly he saw a spaceship and out of it came an alien named KK. Obviously, the alien had a different language and thus couldn't communicate readily. After some psycho-telepathic talk, Sumo realised that KK's language has M distinct characters. And a valid word in his language satisfies the following properties: - Each character in the word must be one of the