/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	{
		Scanner scan 
= new Scanner
(System.
in); 
		do{
			toTest += scan.nextLine();
			if (scan.hasNext()){
				toTest += "\n";
				continue;
			}
		}while (false);
 
		int digitCount = 0, otherCount = 0;
		for (char c : toTest.toCharArray()){
			if (c >= '0' && c <= '9'){
				digitCount++;
			}
			else{
				otherCount++;
			}
		}
		System.
out.
println("Digits: " + digitCount 
+ " Nondigits: " + otherCount
);  
		int f1 = 1, f2 = 2;
 
		while (true){
			if (f2 == digitCount && f1 == otherCount){
				System.
out.
println("Valid program"); 				break;
			}
			int store = f2;
			f2 += f1;
			f1 = store;
 
			if (f1 > digitCount){
				System.
out.
println("Invalid program"); 				break;
			}
		}
	}
}
				LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVN0cmluZyB0b1Rlc3QgPSAiIjsKCQlTY2FubmVyIHNjYW4gPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwoJCQoJCWRvewoJCQl0b1Rlc3QgKz0gc2Nhbi5uZXh0TGluZSgpOwoJCQlpZiAoc2Nhbi5oYXNOZXh0KCkpewoJCQkJdG9UZXN0ICs9ICJcbiI7CgkJCQljb250aW51ZTsKCQkJfQoJCX13aGlsZSAoZmFsc2UpOwoJCQoJCWludCBkaWdpdENvdW50ID0gMCwgb3RoZXJDb3VudCA9IDA7CgkJZm9yIChjaGFyIGMgOiB0b1Rlc3QudG9DaGFyQXJyYXkoKSl7CgkJCWlmIChjID49ICcwJyAmJiBjIDw9ICc5Jyl7CgkJCQlkaWdpdENvdW50Kys7CgkJCX0KCQkJZWxzZXsKCQkJCW90aGVyQ291bnQrKzsKCQkJfQoJCX0KCQlTeXN0ZW0ub3V0LnByaW50bG4oIkRpZ2l0czogIiArIGRpZ2l0Q291bnQgKyAiIE5vbmRpZ2l0czogIiArIG90aGVyQ291bnQpOwoJCQoJCWludCBmMSA9IDEsIGYyID0gMjsKCQkKCQl3aGlsZSAodHJ1ZSl7CgkJCWlmIChmMiA9PSBkaWdpdENvdW50ICYmIGYxID09IG90aGVyQ291bnQpewoJCQkJU3lzdGVtLm91dC5wcmludGxuKCJWYWxpZCBwcm9ncmFtIik7CgkJCQlicmVhazsKCQkJfQoJCQlpbnQgc3RvcmUgPSBmMjsKCQkJZjIgKz0gZjE7CgkJCWYxID0gc3RvcmU7CgkJCQoJCQlpZiAoZjEgPiBkaWdpdENvdW50KXsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbigiSW52YWxpZCBwcm9ncmFtIik7CgkJCQlicmVhazsKCQkJfQoJCX0KCX0KfQ==