import java.time.Duration;
import java.time.Instant;
import java.util.*;
import java.util.function.Function;

public class FDense {
    private static int N = 2; // Size of the alphabet
    private static HashMap<Integer, Integer> Rule= new HashMap<Integer, Integer>();

   private static HashMap<Integer, Integer> createHashMap(char[] rule, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int n = (int) Math.pow(2, k); // Total number of input patterns
        
        // Iterate over all input patterns and store the output in the HashMap
        for (int i = 0; i < n; i++) {
        	hashMap.put(i, Integer.parseInt(String.valueOf(rule[i]).trim()));
        }
        
        return hashMap;
    }
    
    private static List<String> generateWords(int length) {
        List<String> words = new ArrayList<>();
        generateWordsHelper("", length, words);
        return words;
    }

    private static void generateWordsHelper(String prefix, int length, List<String> words) {
        if (prefix.length() == length) {
            words.add(prefix);
        } else {
            for (int i = 0; i < N; i++) {
                generateWordsHelper(prefix + i, length, words);
            }
        }
    }
    
    public static List<String> applyRule(List<String> words, int span) {
        List<String> newWords = new ArrayList<>();
        int  key;
        for (String word : words) {
            StringBuilder newWord = new StringBuilder();
            for (int i = 0; i < word.length(); i++) {
                String pattern = "";
                if(i == word.length() - span + 1) {
                	pattern += word.charAt(i);
                	pattern += word.charAt(i+1); 
                	pattern += word.charAt(i+2);
                	pattern += word.charAt(0);
                } else if (i == word.length() - span + 2) {
                	pattern += word.charAt(i);
                	pattern += word.charAt(i+1); 
                	pattern += word.charAt(0);
                	pattern += word.charAt(1);
                } else if (i == word.length() - span + 3) {
                	pattern += word.charAt(i);
                	pattern += word.charAt(0); 
                	pattern += word.charAt(1);
                	pattern += word.charAt(2);
                } else {
                	pattern += word.charAt(i);
                	pattern += word.charAt(i+1);
                	pattern += word.charAt(i+2);
                	pattern += word.charAt(i+3);
                }
                
                // apply the rule to the input pattern and append the result to the new word
                key = Integer.parseInt(pattern, 2);
                int output = Rule.get(key);
                newWord.append(output);
            }
            newWords.add(newWord.toString());
        }
        return newWords;
    }

    
	public static String applyRule(String word, int span) {
		int key;
		String newWord = "";
		for (int i = 0; i < word.length(); i++) {
			String pattern = "";
			if (i == word.length() - span + 1) {
				pattern += word.charAt(i);
				pattern += word.charAt(i + 1);
				pattern += word.charAt(i + 2);
                pattern += word.charAt(i + 3);
                pattern += word.charAt(i + 4);
				pattern += word.charAt(0);
			} else if (i == word.length() - span + 2) {
				pattern += word.charAt(i);
				pattern += word.charAt(i + 1);
                pattern += word.charAt(i + 2);
				pattern += word.charAt(i + 3);
				pattern += word.charAt(0);
				pattern += word.charAt(1);
			} else if (i == word.length() - span + 3) {
				pattern += word.charAt(i);
                pattern += word.charAt(i + 1);
                pattern += word.charAt(i + 2);
				pattern += word.charAt(0);
				pattern += word.charAt(1);
				pattern += word.charAt(2);
			} else if (i == word.length() - span + 4) {
                pattern += word.charAt(i);
                pattern += word.charAt(i + 1);
				pattern += word.charAt(0);
				pattern += word.charAt(1);
				pattern += word.charAt(2);
                pattern += word.charAt(3);
            } else if (i == word.length() -span + 5) {
                pattern += word.charAt(i);
				pattern += word.charAt(0);
				pattern += word.charAt(1);
				pattern += word.charAt(2);
                pattern += word.charAt(3);
                pattern += word.charAt(4);
            } else {
				pattern += word.charAt(i);
				pattern += word.charAt(i + 1);
				pattern += word.charAt(i + 2);
				pattern += word.charAt(i + 3);
                pattern += word.charAt(i + 4);
                pattern += word.charAt(i + 5);
			}

			// apply the rule to the input pattern and append the result to the new word
			key = Integer.parseInt(pattern, 2);
			newWord += Rule.get(key);
		}

		return newWord;
	}
    
    public static void main(String[] args) {
		int k = 15;
		int m = 10;
		int span = 6;
		
		List<String> originalWords = new ArrayList<>();
		List<String> wordsWithKperiod = new ArrayList<>();
		List<String> allWords = new ArrayList<>();
		
		originalWords = generateWords(m);
		
		//System.out.println(originalWords);
		
		wordsWithKperiod = generateWords(k-m);
		
		for (int i = 0; i < originalWords.size(); i++) {
			for (int j = 0; j < wordsWithKperiod.size(); j++) {
				allWords.add(originalWords.get(i) + wordsWithKperiod.get(j));
			}
		}
		

		/*
		for (int i = 0; i < originalWords.size(); i++) {
			for (int j = 0; j < wordsWithKperiod.size(); j++) {
				String newWord = originalWords.get(i) + wordsWithKperiod.get(j);
				newWord += newWord.substring(0, span); // add first k characters to end of string
				allWords.add(newWord);
			}
		}
		*/
		
		//testing
		System.out.println(allWords);
		
		String tabularRule = "1010101001010101010101010101010101010101101010101010101010101010";
		Rule = createHashMap(tabularRule.toCharArray(), span);
		System.out.println(Rule);
		
		
		int mdense = 0; 
        
		for(int z = 0; z < allWords.size(); z++) {
			String newWord = applyRule(allWords.get(z), span);
			while(!newWord.equals(allWords.get(z))) {
				newWord = applyRule(newWord, span);
			}
 			mdense += 1;
		}
		
        System.out.println(mdense);
		
	}
}